Re: Halting Problem

Pascal J. Bourguignon wrote:

It seems to me that you are confusing several levels, several
different problems.

Good point. I should have restricted the discussion to only theoretical
computers (infinite time and infinite memory).

What we can say, is that it is trivial to write a predicate unloopy(x)
indicating that a program x contains no indefinite loop or recursion.

unloopy(x) ==> halts(x).

This is basically what you are talking about.


Not true. As Mr. Steinbach pointed out elsewhere in this thread, there
are two types of recursion being discussed, and again it is my fault for
being unclear about the distinction. One is a function calling itself.
Let's call that "functional" recursion. This type of recursion can be
reduced to a simple loop of some sort, as you explained. And my example
of the poor soul's attempted solution takes this kind of recursion into
account. More on this just below.

The other, troubling type of recursion is the "logical" recursion by
which a program to be tested for halting actually calls the "halts()"
function itself. This is the category that I was referring to at the
end of my original post, when I said:

"Could we then further conclude that the halting problem is only
undecidable for SOME recursive programs, and even for these programs,
the condition of undecidability can at least be detected?"

And at the risk of confusing the discussion a little more, I actually
think that even this class of programs are actually decidable. I also
think that I'm probably wrong, but I have to work through the thought
experiment. I'll postpone that for everyone's benefit. :)

Back to the topic of loops (equivalently, "functional" recursion).

Your example:

hotpo(n) = if odd(n) then 3*n+1 else n/2 end

hotpoto(n):
while n>1 do
n := hotpo(n)
done

halts(hotpoto) ?

Here is what a compiler might do (still working in the realm of
theoretical computers) with this code. A good compiler would "inline"
the hotpo(n) function because it's non-recursive and small. So our
first pass might yield:

hotpoto(n):
while (n > 1) do
if (n & 1) then
n = 3 * n + 1
else
n = n / 2
end
done

Compilation of this into an arbitrary assembly language might yield:

1: mov a, [n] // copy contents of memory "n" into register "a"
2: cmp a, 1 // compare register "a" to immediate value "1"
3: jle 11 // jump if less or equal
4: test a, 1 // logical AND with immediate value "1"
5: jnz 9 // jump if result not zero
6: mult a, 3 // multiply
7: add a, 1 // add
8: jmp 2 // back to the beginning of the "while" loop
9: div a, 2 // divide
10: jmp 2 // back to the beginning of the "while" loop
11: end

I won't attempt ASCII art of what the branch tree would look like. But
it would have line 11 as the only "leaf" node, and its only parent would
be line 3. The other child of line 3 is line 4 (jump not taken). The
only other conditional branch is line 5, whose children are lines lines
6 and 9. It's a pretty simple tree.

It's a good example, because there isn't much simplification that can be
done. The "halts()" function would essentially be forced to execute the
entire thing, iteratively. If the leaf node is reached, then "yes," the
program does halt. If either of the two conditional branch nodes is
ever reached AND the value of "a" is something that we've seen before,
then "no," the program does not halt. Since we have infinite memory, we
can keep track of all the states "a" has held every time we've
encountered each of the two conditional branches.

This theoretical computer must use some format (number of bits) to store
integers, giving "n" a finite number of states. This ensures that
either the "yes" or "no" condition above WILL be encountered. The
"halts()" function will always halt for this example program, for any
"n," and will always produce a "yes" or "no" answer.

I suppose the exception to this logic is that "n" could have an infinite
number of bits, since this is a theoretical computer with infinite
memory. But that argument seems a bit trivial... Just performing an
"add" operation on two infinitely large numbers would take an infinite
amount of time. I would go a step further to say that if such a
scenario (infintely large numbers) is required to make the halting
problem undecidable, then the halting problem doesn't have much (any?)
practical application. This is a very unsatisfactory conclusion,
though, and I'd be much happier to learn that I simply have made a
logical error in reaching it.
.

Relevant Pages

  • Re: qsort
    ... On a system with infinite available ... >> memory, it will never terminate. ... In the real world, infinite recursion ... Since qsort() in particular is likely ...
    (comp.lang.c)
  • Re: Raatikainens critique of Chaitin
    ... dealing with exponential Diophantine equations was ... A subset S of N is bi-immune for a class C if S is infinite but does ... You couldn't have a bi-immunity result for the problem of whether ... Bi-immunity was a concept from the early years of recursion theory, ...
    (sci.math)
  • Re: Set Theory: Should You Believe
    ... there is such a thing as an infinite tape, ... existence of an infinite tape is no different from assuming that people ... infinite memory computers cannot really be built. ... In practice, no brute force method is remotely practical. ...
    (sci.logic)
  • Re: Steps beyond "Hello World" program
    ... This is what Turing meant. ... > how much memory is available on the network, ... no solvable problem requires an infinite amount of memory. ... I agree that if you had such a construction rule then ...
    (comp.programming)
  • Re: turing completeness
    ... claim that the tape *must* be infinite. ... >>The Turing Machine just needs to be able at will to drive to CompUsa ... computer runs out of memory its operating system aborts the TM ...
    (comp.programming)
Loading