Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > The halting problem revisited

Reply
Thread Tools

The halting problem revisited

 
 
Roedy Green
Guest
Posts: n/a
 
      03-26-2011
The proof that the halting problem is insoluble has discouraged any
sort work on static analysing what computer programs will do.

What if the problem were reformulated like this:

The input to the detector is a Java program, syntactically valid. The
output is :

1. definitely halts
2. definitely does not halt
3. can't tell

Obviously such a program CAN be written. The question is how high
quality is such a detector?

What counts is the percentage of real-life programs that fall in
category 1 or 2.

It does not really matter how it fairs with pathological constructions
favoured of mathematicians.

There is some research in this area, going on in the name of code
optimisation, where you do analysis on a fairly local basis.

You might imagine a compiler warning you of parts of your program
where you have created an endless loop or endless recursion under some
unusual run time conditions. It would not necessarily catch
everything, but it might catch something.


--
Roedy Green Canadian Mind Products
http://mindprod.com
There are only two industries that refer to their customers as "users".
~ Edward Tufte

 
Reply With Quote
 
 
 
 
Lawrence D'Oliveiro
Guest
Posts: n/a
 
      03-26-2011
In message <(E-Mail Removed)>, Roedy Green wrote:

> The proof that the halting problem is insoluble has discouraged any
> sort work on static analysing what computer programs will do.


If that were true, we wouldn’t have optimizing compilers.

> What if the problem were reformulated like this:
>
> The input to the detector is a Java program, syntactically valid. The
> output is :
>
> 1. definitely halts
> 2. definitely does not halt
> 3. can't tell
>
> Obviously such a program CAN be written.


Trivially always answer 3.

> The question is how high quality is such a detector?


Can’t tell.
 
Reply With Quote
 
 
 
 
Alex Mentis
Guest
Posts: n/a
 
      03-26-2011
Lawrence D'Oliveiro wrote:

> > The question is how high quality is such a detector?

>
> Can’t tell.


hehe

 
Reply With Quote
 
Lew
Guest
Posts: n/a
 
      03-26-2011
On 03/26/2011 02:45 AM, Roedy Green wrote:
> The proof that the halting problem is insoluble has discouraged any
> sort work on static analysing what computer programs will do.


"I'm ... well ... ummm ..., just not - er - sure how I ... um, ... feel about
Turing," Tom said haltingly.

--
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedi.../c/cf/Friz.jpg
 
Reply With Quote
 
Joshua Cranmer
Guest
Posts: n/a
 
      03-26-2011
On 03/26/2011 02:45 AM, Roedy Green wrote:
> The proof that the halting problem is insoluble has discouraged any
> sort work on static analysing what computer programs will do.


No it hasn't. Static analysis is a very hot topic of research in
compilers, despite the fact that is provably impossible. In fact, I
would wager that computer science is the only field where we try to
solve problems we already know to be impossible (well, there's also
government, but that doesn't count).

> What if the problem were reformulated like this:
>
> The input to the detector is a Java program, syntactically valid. The
> output is :
>
> 1. definitely halts
> 2. definitely does not halt
> 3. can't tell
>
> Obviously such a program CAN be written. The question is how high
> quality is such a detector?


No, the question is how useful is the definite yes/no compared to the
amount of time it takes to run. Also, it turns out that the halting
problem is actually rather boring for static analysis; perhaps the most
important question in general would either be the equivalency question
(are these two expressions equivalent) or pointer aliasing (can these
pointers point to the same value). Or, if you are looking at
machine/assembly code, the most important question is code/data separation.

> You might imagine a compiler warning you of parts of your program
> where you have created an endless loop or endless recursion under some
> unusual run time conditions. It would not necessarily catch
> everything, but it might catch something.


Sometimes, though, you want an infinite loop. Think of the event loop in
a GUI toolkit.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
 
Reply With Quote
 
Lew
Guest
Posts: n/a
 
      03-26-2011
Roedy Green wrote:
> The input to the detector is a Java program, syntactically valid. The
> output is :
>
> 1. definitely halts
> 2. definitely does not halt
> 3. can't tell
>
> Obviously such a program CAN be written. The question is how high
> quality is such a detector?


That is very far from obvious. You assume that the decider will halt.

Now if #3 were "can't tell within period /x/", that'd be different.

Joshua Cranmer wrote:
> Roedy Green wrote:
>> The proof that the halting problem is insoluble has discouraged any
>> sort work on static analysing what computer programs will do.


> No it hasn't. Static analysis is a very hot topic of research in compilers,
> despite the fact that is provably impossible. In fact, I would wager that
> computer science is the only field where we try to solve problems we already
> know to be impossible (well, there's also government, but that doesn't count).


False analysis. The government doesn't try to solve problems, irrespective of
whether they are possible.

Seriously, though, just because a problem isn't ultimately solvable doesn't
mean that research into heuristics or more efficient approaches or bounding
problems or probabilistic approaches won't be fruitful.

For example, suppose you could prove that a decider has a 99.5% probability of
proving haltability or the impossibility thereof within /x/ seconds. You can
prove that the decider will halt by adding the constraint that it must end
after /x/ seconds. You then call the answer "can't tell" with an epsilon
probability of being wrong.

I should think the impossibility of the theoretical would in no wise
discourage the search for the profitable.

--
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedi.../c/cf/Friz.jpg
 
Reply With Quote
 
Joshua Cranmer
Guest
Posts: n/a
 
      03-26-2011
On 03/26/2011 02:46 PM, Lew wrote:
> Roedy Green wrote:
>> The input to the detector is a Java program, syntactically valid. The
>> output is :
>>
>> 1. definitely halts
>> 2. definitely does not halt
>> 3. can't tell
>>
>> Obviously such a program CAN be written. The question is how high
>> quality is such a detector?

>
> That is very far from obvious. You assume that the decider will halt.


Program A:
Always returns "can't tell" for any input.

Program B:
Looks for a for/while/do-while loop in the code. If one is present,
output "can't tell". Otherwise, check a method callgraph for the
presence of a cycle. If one is present, output "can't tell", otherwise,
output "definitely does not halt"

Program A clearly satisfies the requirements of the detector, in that it
is never wrong. Obviously, it always terminates, so there is an obvious
program (at least to me) that satisfies the requirements.

Program B is a program which is moderately more useful but still
satisfies the requirements.

So it seems quite obvious that it exists, at least to me.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
 
Reply With Quote
 
Lew
Guest
Posts: n/a
 
      03-26-2011
Joshua Cranmer wrote:
> Lew wrote:
>> Roedy Green wrote:
>>> The input to the detector is a Java program, syntactically valid. The
>>> output is :
>>>
>>> 1. definitely halts
>>> 2. definitely does not halt
>>> 3. can't tell
>>>
>>> Obviously such a program CAN be written. The question is how high
>>> quality is such a detector?

>>
>> That is very far from obvious. You assume that the decider will halt.

>
> Program A:
> Always returns "can't tell" for any input.
>
> Program B:
> Looks for a for/while/do-while loop in the code. If one is present, output
> "can't tell". Otherwise, check a method callgraph for the presence of a cycle.
> If one is present, output "can't tell", otherwise, output "definitely does not
> halt"
>
> Program A clearly satisfies the requirements of the detector, in that it is
> never wrong. Obviously, it always terminates, so there is an obvious program
> (at least to me) that satisfies the requirements.
>
> Program B is a program which is moderately more useful but still satisfies the
> requirements.
>
> So it seems quite obvious that it exists, at least to me.


Silly me. I assumed we wanted it to produce a *correct* answer based on an
actual effort to determine the answer.

Now that I look again, I see that attempts at correct results were not
explicitly specified. What was I /thinking/?

Will program B always succeed? Now that I hear your answer it's no longer not
obvious.

--
Lew
Honi soit qui mal y pense.
http://upload.wikimedia.org/wikipedi.../c/cf/Friz.jpg
 
Reply With Quote
 
Dirk Bruere at NeoPax
Guest
Posts: n/a
 
      03-26-2011
On 26/03/2011 07:07, Lawrence D'Oliveiro wrote:
> In message<(E-Mail Removed) >, Roedy Green wrote:
>
>> The proof that the halting problem is insoluble has discouraged any
>> sort work on static analysing what computer programs will do.

>
> If that were true, we wouldn’t have optimizing compilers.
>
>> What if the problem were reformulated like this:
>>
>> The input to the detector is a Java program, syntactically valid. The
>> output is :
>>
>> 1. definitely halts
>> 2. definitely does not halt
>> 3. can't tell
>>
>> Obviously such a program CAN be written.

>
> Trivially always answer 3.


No.
What cannot be done is to create an algorithm that will tell in all
cases whether a program will halt.

It is trivial to detect whether most small programs will do in a finite
time. Otherwise nobody could ever read somebody else's code and spot
halting/loop bugs. The Human brain is also subject to the Turing
limitation (as far as is known)

--
Dirk

http://www.neopax.com/technomage/ - My new book - Magick and Technology
 
Reply With Quote
 
Joshua Cranmer
Guest
Posts: n/a
 
      03-26-2011
On 03/26/2011 04:53 PM, Lew wrote:
> Will program B always succeed? Now that I hear your answer it's no
> longer not obvious.


If you make the modification that I had (I mixed up "definitely halts"
with "definitely does not halt"), yes, with the added caveat that if you
cannot construct the callgraph, you print out "can't tell." The reasons
for such might include native methods, effects of reflection, violation
of the closed world assumption, or multithreaded pitfalls (viewing the
callgraph at an actual instruction level, so context switches become
extra edges--I'm viewing this as its correlation to a Turing machine).

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
GetTransferData() works only after halting over a breakpoint dushkin Java 0 04-23-2006 03:40 PM
Re: Yet another Attempt at Disproving the Halting Problem Peter Olcott C++ 245 08-21-2004 04:48 PM
Re: Halting Problem: Give up >parr\(*> C++ 10 08-16-2004 10:18 PM
Solution to the halting Problem? Peter Olcott C++ 117 08-10-2004 09:39 PM
Refutation of the DisProof of the Halting Problem Peter Olcott C++ 31 08-02-2004 04:04 PM



Advertisments