halting is weak?
Author Message
halting is weak?

A nice one line proof of halting(?):
H(P) is the proposed program which returns true if program P halts.  Then
program A = ``L: if H(A) goto L''
which is results in the contradiction.

My questions:
This contradiction relies on the program A calling the halting program
as a subroutine.  To me, this is a weak result -- it does not seem
to forbid the possibility of there being a halting test program H() that
works for all programs that do not call H() as a subroutine.

- The set of possible programs that do not call H() is large and significant;
- the set of programs that call H() seems to me to be (relatively) small
(albeit infinite, i.e. set of measure zero maybe), and perhaps not
significant (is there any use for these programs other than as an
element in the halting proof?)

Thus the halting theorem seems to me to be weak and insignificant.

Please explain the flaw in my understanding.
thanks

Sun, 19 Jul 1998 03:00:00 GMT
halting is weak?

Quote:

>A nice one line proof of halting(?):
>H(P) is the proposed program which returns true if program P halts.  Then
>program A = ``L: if H(A) goto L''
>which is results in the contradiction.

>My questions:
>This contradiction relies on the program A calling the halting program
>as a subroutine.  To me, this is a weak result -- it does not seem
>to forbid the possibility of there being a halting test program H() that
>works for all programs that do not call H() as a subroutine.

>- The set of possible programs that do not call H() is large and significant;
>- the set of programs that call H() seems to me to be (relatively) small
>  (albeit infinite, i.e. set of measure zero maybe), and perhaps not
>  significant (is there any use for these programs other than as an
>  element in the halting proof?)

>Thus the halting theorem seems to me to be weak and insignificant.

>Please explain the flaw in my understanding.
>thanks

Take the following as a grain of salt, as my understanding of the matter
is hardly perfect.

A problem lies in your division of programs between those that call H()
and those that don't.  You appear to have eliminated the self-reference
caused when H() processes an arbitrary program, but in fact you really
haven't.  This is where Goedel's Theorem enters.  If your language is
sufficiently powerful (I'm regarding a programming language as a formal
system here--please forgive me), then there exist alternate ways of
causing self-reference in the processing of your program by H().  The
only way to prevent this is to restrict the generality of your language.

This is a encapsulated summary and I have likely made an error; for an
entertaining and educational look at these issues, check out Douglas
Hofstadter's book _Goedel, Escher, Bach: an Eternal Golden Braid_.

--Mark

--

Indiana University CS Dept.      |  forgive us now for     - Jim Morrison
Bloomington, Indiana, USA        |  wasting the dawn.

Mon, 20 Jul 1998 03:00:00 GMT
halting is weak?

Quote:

>Furthermore, many of the computability theorems are based on the idealized
>Turing Machine, which has an infinite tape.  When applied to real computer
>systems they don't apply, since all real systems have finite memory
>capacities.

I wish people would quit spouting this untruth.  Turing Machines DO NOT
use an infinite tape, only an unbounded one.  A Turing Machine that halts
after N steps can have used at most N units of tape.  A real computer is
unbounded in exactly the same way, as long as you are willing to manufacture
and mount yet one one disk or magtape when ever it needs it.

--
Mark Biggar

Mon, 20 Jul 1998 03:00:00 GMT
halting is weak?

Quote:

>This contradiction relies on the program A calling the halting program
>as a subroutine.  To me, this is a weak result -- it does not seem
>to forbid the possibility of there being a halting test program H() that
>works for all programs that do not call H() as a subroutine.

This dependence on A calling H() is necessary for this particular proof of
the halting theorem.  I suspect that other proofs can be constructed that
don't rely on it, but they wouldn't be nearly as simple.

Quote:
>- The set of possible programs that do not call H() is large and significant;

But even if there isn't a proof that doesn't involve this self-reference, I
think your division of programs into "significant" and "insignificant" is
rather arbitrary.  The halting theorem isn't intended to be about actual
computer programs, but about *all* computer programs.  In fact, I think
it's pretty well recognized that a halting program that worked for most
real-world computer programs could be written.

Furthermore, many of the computability theorems are based on the idealized
Turing Machine, which has an infinite tape.  When applied to real computer
systems they don't apply, since all real systems have finite memory
capacities.
--
Barry Margolin
BBN PlaNET Corporation, Cambridge, MA

Phone (617) 873-3126 - Fax (617) 873-6351

Mon, 20 Jul 1998 03:00:00 GMT
halting is weak?
I have removed comp.theory from the list of newsgroups, because
they don't need to hear yet another exposition of the halting
problem.

Quote:

>This contradiction relies on the program A calling the halting program
>as a subroutine.  To me, this is a weak result -- it does not seem
>to forbid the possibility of there being a halting test program H() that
>works for all programs that do not call H() as a subroutine.

The undecidability of the halting problem does not mean that we
cannot tell whether any particular program halts.  In fact, there
are large classes of programs for which the halting problem is
decidable.

That hardly means that the undecidability of the halting problem
is a "weak and insignificant" result.  It is perhaps the most
significant result in all of computer science.

You seem to be overlooking the fact that the counterexample works
for *all* programs H, not just the particular program H that you
happen to be thinking of at the moment.  Since H ranges over
*all* programs, *every* program contains one of those H's as a
subprogram.

By the way, the short proof you cited is not a complete proof.
In a real proof you must show that, for every program H, you can
write a program A such that A is equivalent to ``L: if H(a) goto L'',
where ``a'' is a standard representation of A.  This is scarcely
obvious, since there is a sense in which the program A contains
itself as a proper subprogram.  As a syntactic matter, this is
impossible.  That's why words like "equivalent" and "representation"
matter.  This part of the proof is closely related to the problem of
writing a self-reproducing program.

William D Clinger

Tue, 21 Jul 1998 03:00:00 GMT
halting is weak?

>This contradiction relies on the program A calling the halting program
>as a subroutine.  To me, this is a weak result -- it does not seem
>to forbid the possibility of there being a halting test program H() that
>works for all programs that do not call H() as a subroutine.

This dependence on A calling H() is necessary for this particular proof of
the halting theorem.  I suspect that other proofs can be constructed that
don't rely on it, but they wouldn't be nearly as simple.

Well, this proof isn't actually that simple, because it avoided
discussing the only hard part: being able to define the
self-inspecting program A.  (Well, H inspects A, but H is called as a
subroutine of A.)  A serves as code and as data, and one has to show
that such a construction is possible in the underlying framework of
your choice (e.g., Turing Machines, mu-recursive functions, ...).

The crucial insight is the possibility of a Univeral Turing Machine;
if this already is a given, then proving undecidability of the halting
problem is rather trivial indeed.

Furthermore, many of the computability theorems are based on the idealized
Turing Machine, which has an infinite tape.  When applied to real computer
systems they don't apply, since all real systems have finite memory
capacities.

This comes up every once in a while, but it is irrelevant.  Even
though "real" machines have only finite memory (and could therefore be
considered FSMs), their state space is so mind-boggingly huge, that
the theoretically possible decision procedure would run much longer
than any real computer would be able to host it.

--
-Matthias

Tue, 21 Jul 1998 03:00:00 GMT
halting is weak?

Quote:

>>Furthermore, many of the computability theorems are based on the idealized
>>Turing Machine, which has an infinite tape.  When applied to real computer
>>systems they don't apply, since all real systems have finite memory
>>capacities.

>I wish people would quit spouting this untruth.  Turing Machines DO NOT
>use an infinite tape, only an unbounded one.  A Turing Machine that halts
>after N steps can have used at most N units of tape.  A real computer is
>unbounded in exactly the same way, as long as you are willing to manufacture
>and mount yet one one disk or magtape when ever it needs it.

Unfortunately, a _new_ disk or magtape is needed; you cannot re-use
any.  For any N, there are TM terminating computations that need more than
N units of tape.  N could exceed the number of elementary particles in the
Universe.

So 'unbounded' is physically unattainable.  Strictly speaking, any
computer, or even all existing ones networked together, would be no more
than a Finite Automaton.  The number of states would be astronomical, but
so what.

On the other hand, 'idealizations' like Pushdown Automata and Turing
machines are very useful... an analogous situation with R (the reals),
continuous functions on R, and so on.

Ilias

Thu, 23 Jul 1998 03:00:00 GMT
halting is weak?

Quote:

>A nice one line proof of halting(?):
>H(P) is the proposed program which returns true if program P halts.  Then
>program A = ``L: if H(A) goto L''
>which is results in the contradiction.

>My questions:
>This contradiction relies on the program A calling the halting program
>as a subroutine.  To me, this is a weak result -- it does not seem
>to forbid the possibility of there being a halting test program H() that
>works for all programs that do not call H() as a subroutine.

>- The set of possible programs that do not call H() is large and significant;
>- the set of programs that call H() seems to me to be (relatively) small
>  (albeit infinite, i.e. set of measure zero maybe), and perhaps not
>  significant (is there any use for these programs other than as an
>  element in the halting proof?)

>Thus the halting theorem seems to me to be weak and insignificant.

>Please explain the flaw in my understanding.
>thanks

No, we cannot say that the unsolvable Halting Problem is "solvable but
for epsilon".  The short proof is nice but could be misleading.   Here is
an elementary account of pertinent facts.

The set H of halting computations, encoded in the integers, is a Sigma-
0-1 (rec. enumerable) set.  The set computed by any (terminating!) algorithm
is a Delta-0-1 (recursive) set, by definition.

H happens to be a "complete" Sigma-0-1 set (it "encodes" all Sigma-0-1
sets) and from this one shows H is not Delta-0-1.  That is the unsolvabili-
ty of the Halting Problem.

One way to understand "complete": _any_ Sigma-0-1 set can be obtained
as the set of n's for which a certain Turing machine halts.  In fact, this
means they are 'semi-decidable': there is an algorithm that given k, halts
and answers 'yes' if k is in the set.  But in general it fails to terminate
if k is not in the set... and we don't know what to conclude; it might be
that on any given input the TM will terminate 'if we wait a little longer'
... and then again, it might never do so.

It also follows that a set is computable (Delta-0-1) if and only if
both the set and its complement are Sigma-0-1.  Again, this is much less
innocent than it sounds!

There is a lot of 'difference' between H and any given computable (i.e.
Delta-0-1) set R.  This can be seen from the closure properties of Delta-0-1
E.g. adjoining or removing a finite set to/from R yields another computable
set and hence not H.  Adjoining infinitely many elements to R, that form a
computable set R', does the same.  Any finite union (or intersection) of R
sets still yields a computable set; none of these manages to "approximate"
H any better; what is left over, H - R, is of the "same" complexity as H.

What about using infinitely many R's... a countable family R_1, R_2 ...
of computable sets?   We could consider a _computable family_ and take its
union, say.  This means: there is an algorithm that for any n specifies a
computable set R_n -- perhaps by generating an algorithm P_n that computes
R_n... P_n answers yes or no to any question "is m in R_ n?".  Too bad...
such a union is still computable.. a Delta-0-1 set R.  In fact what I just
described is an algorithm for R.

It just cannot be done... a gulf separates H from any R.  H can in fact
be expressed as _some_ countable union of R's, an uncomputable family...
but this has 0 value and is really a triviality; after all, H is the coun-
table union of singletons (m), for the m that belong to H...

No useful 'reduction' is known.  It is a strange world... Remember,
for any TM that computes a function, there are infinitely many other TM's
that compute the same function.  Knowing the first k values f(0), ... f(k-1)
of a computable function f for some k gives _no_ information about the
other values of f... or even just about the next value, f(k).

Limited halting problems are solvable -- by restricting attention to
specifiable subsets of the set of computable functions.  But it is useless
to think of them as "approximations" to H... after all, they are Delta-0-1,
good old R sets themselves!

Ilias

Thu, 23 Jul 1998 03:00:00 GMT
halting is weak?

Barry> think it's pretty well recognized that a halting program
Barry> that worked for most real-world computer programs could be
Barry> written.

You really think so? I can think of whole classes of programs for
which this is clearly not the case. Take for example a program
modelling a chaotic system, which halts if and only if some modelled
variable crosses some threshold. Inferring this kind of emergent
behavior from a relatively simple piece of code would be pretty difficult.

Jake

Fri, 24 Jul 1998 03:00:00 GMT
halting is weak?

Quote:

>>>Furthermore, many of the computability theorems are based on the idealized
>>>Turing Machine, which has an infinite tape.  When applied to real computer
>>>systems they don't apply, since all real systems have finite memory
>>>capacities.

>>I wish people would quit spouting this untruth.  Turing Machines DO NOT
>>use an infinite tape, only an unbounded one.  A Turing Machine that halts
>>after N steps can have used at most N units of tape.  A real computer is
>>unbounded in exactly the same way, as long as you are willing to manufacture
>>and mount yet one one disk or magtape when ever it needs it.

>    Unfortunately, a _new_ disk or magtape is needed; you cannot re-use
>   any.  For any N, there are TM terminating computations that need more than
>   N units of tape.  N could exceed the number of elementary particles in the
>   Universe.

>    So 'unbounded' is physically unattainable.  Strictly speaking, any
>   computer, or even all existing ones networked together, would be no more
>   than a Finite Automaton.  The number of states would be astronomical, but
>   so what.

>    On the other hand, 'idealizations' like Pushdown Automata and Turing
>   machines are very useful... an analogous situation with R (the reals),
>   continuous functions on R, and so on.

>                                                    Ilias

i think this machines are always bounded stuff is kind of silly.
one way to see this is to consider software. a software program
could be written (using arbitrary arithmetic,etc.) which could
run on any machine no matter how big or small, in one of many
currently available languages.
are we interested in the properties of this software program?
yes.
does machines are always bounded affect our discussion of this
program?
perhaps, but not really (ie. the program might crash due to
limits not inherent in the program).

Sat, 25 Jul 1998 03:00:00 GMT
halting is weak?

Quote:

>>>>Furthermore, many of the computability theorems are based on the idealized
>>>>Turing Machine, which has an infinite tape.  When applied to real computer
>>>>systems they don't apply, since all real systems have finite memory
>>>>capacities.

>>>I wish people would quit spouting this untruth.  Turing Machines DO NOT
>>>use an infinite tape, only an unbounded one.  A Turing Machine that halts
>>>after N steps can have used at most N units of tape.  A real computer is
>>>unbounded in exactly the same way, as long as you are willing to manufacture
>>>and mount yet one one disk or magtape when ever it needs it.

>>        Unfortunately, a _new_ disk or magtape is needed; you cannot re-use
>>   any.  For any N, there are TM terminating computations that need more than
>>   N units of tape.  N could exceed the number of elementary particles in the
>>   Universe.

>>        So 'unbounded' is physically unattainable.  Strictly speaking, any
>>   computer, or even all existing ones networked together, would be no more
>>   than a Finite Automaton.  The number of states would be astronomical, but
>>   so what.

>>        On the other hand, 'idealizations' like Pushdown Automata and Turing
>>   machines are very useful... an analogous situation with R (the reals),
>>   continuous functions on R, and so on.

Does the "finiteness" of a real computer change in any way if you
program it in one of the newer functional languages that use lazy evaluation?
IIRC one of the applications of this technique is that it allows you to
reasonably represent certain kinds of infinite data structures.

--
Nicholas Weininger

"If all mankind minus one were of one opinion, and only one person were of the
contrary opinion, mankind would be no more justified in silencing that one
person, than he, if he had the power, would be justified in silencing mankind."
-John Stuart Mill

Sun, 26 Jul 1998 03:00:00 GMT
halting is weak?

:
:     Barry> think it's pretty well recognized that a halting program
:     Barry> that worked for most real-world computer programs could be
:     Barry> written.
:
: You really think so? I can think of whole classes of programs for
: which this is clearly not the case. Take for example a program
: modelling a chaotic system, which halts if and only if some modelled
: variable crosses some threshold. Inferring this kind of emergent
: behavior from a relatively simple piece of code would be pretty difficult.

In theory, any real computer can be modeled as an FSM.  So, in theory,
you can always analyze such a beastly FSM and figure out exactly what
it will do.  There are only so many bits that can change on a computer;
all of memory, and all of the external storage.  So, by "simply" keeping
track of configurations, one can "easily" detect infinite loops. Also,
since it "only an FSM", we can also predict many more characteristics and
all that.  There are some glitches relating to time/space requirements as
they relate to certain metrics of the universe and that kind of stuff, but
I am sure they'll be addressed in the next release of the universe :-)
--
Antoun (Tony) Kanawati

http://www.{*filter*}com.net/~tonyk/

Sun, 26 Jul 1998 03:00:00 GMT
halting is weak?

: i think this machines are always bounded stuff is kind of silly.
: one way to see this is to consider software. a software program
: could be written (using arbitrary arithmetic,etc.) which could
: run on any machine no matter how big or small, in one of many
: currently available languages.
: are we interested in the properties of this software program?
: yes.
: does machines are always bounded affect our discussion of this
: program?
: perhaps, but not really (ie. the program might crash due to
: limits not inherent in the program).

The analysis of real software is a software engineering problem,
whereas the decidability of program characteristics (halting, kind
of language accepted, etc...) are theoretical issues.  The theory
helps us establish the limits of the practice, but it does not
automatically translate.  Real programs on real computers are very
different from universal turing machines and input tapes.  Sorta
like infinitely thin beams and point loads vs. real concrete and
steel beams and real loads.  The mathematically tractable model of
beams and loads helps, but it takes a lot more to get a real beam
designed and constructed, and a lot of that depends on purely
empirical experience about the placement of steel bars, the drying
of concrete, various material properties, the weather, and all kinds
of things.

So, if you know that in the simple world of Turing machines and
unbounded resources, it is not possible to decide much about
programs (a 7 state universal turing machine), you can rest assured
that the problem is quite difficult on a real computer; a real computer
has an astronomically high number of distinct states, and very large
resources, and that's close enough to the ideal model.  Clearly, the
approximation is not precise, since even astronomically large integers
are ultimately finite, but it's good enough for all practical purposes,
for the same reasons that an infinitely thin beam and various assumptions
about nice linear elastic behavior are acceptable for structural
design and analysis: they're good enough approximations of reality
(modulo some safety factors, of course).
--
Antoun (Tony) Kanawati

http://www.{*filter*}com.net/~tonyk/

Sun, 26 Jul 1998 03:00:00 GMT
halting is weak?

Quote:

>: i think this machines are always bounded stuff is kind of silly.
>: one way to see this is to consider software. a software program
>: could be written (using arbitrary arithmetic,etc.) which could
>: run on any machine no matter how big or small, in one of many
>: currently available languages.
>: are we interested in the properties of this software program?
>: yes.
>: does machines are always bounded affect our discussion of this
>: program?
>: perhaps, but not really (ie. the program might crash due to
>: limits not inherent in the program).

>The analysis of real software is a software engineering problem,
>whereas the decidability of program characteristics (halting, kind
>of language accepted, etc...) are theoretical issues.  The theory
>helps us establish the limits of the practice, but it does not
>automatically translate.  Real programs on real computers are very
>different from universal turing machines and input tapes.  Sorta
>like infinitely thin beams and point loads vs. real concrete and
>steel beams and real loads.  The mathematically tractable model of
>beams and loads helps, but it takes a lot more to get a real beam
>designed and constructed, and a lot of that depends on purely
>empirical experience about the placement of steel bars, the drying
>of concrete, various material properties, the weather, and all kinds
>of things.

>So, if you know that in the simple world of Turing machines and
>unbounded resources, it is not possible to decide much about
>programs (a 7 state universal turing machine), you can rest assured
>that the problem is quite difficult on a real computer; a real computer
>has an astronomically high number of distinct states, and very large
>resources, and that's close enough to the ideal model.  Clearly, the
>approximation is not precise, since even astronomically large integers
>are ultimately finite, but it's good enough for all practical purposes,
>for the same reasons that an infinitely thin beam and various assumptions
>about nice linear elastic behavior are acceptable for structural
>design and analysis: they're good enough approximations of reality
>(modulo some safety factors, of course).
>--
>Antoun (Tony) Kanawati

>http://www.{*filter*}com.net/~tonyk/

True, but if what your saying is "when writing real programs we
can make assumptions about the particular implementation we
may be running on" you're asking for trouble, this is what leads
to non-portable code,etc.. if it is possible  (ie. you're not writing
a device driver or something)  to write your program
in terms of some abstract machine (RAM machine for example) you
will never have to worry about the particulars of implementation
and will probably wind up with a nice piece of code. I always
try to write my code in terms of abstract machines (unless there
is a compelling reason not to (performance,etc.)) and feel that
are some very compelling reasons to do so.
when faced with decision whether or not to put some concrete
limitation on your program, you should give it a long hard look
before doing so. i write tons of software and in find that in
many practical problems one can write "abstract" code, and to
not write abstract code could be considered a blunder, to say
that abstract machines really are not practical is just not
true! (rams are really quite flexible (and languages written
for them)!)
ben

Sun, 26 Jul 1998 03:00:00 GMT
halting is weak?
Could I point out that there is an interesting class of programs for which
it _is_ possible to solve the halting problem?

Second-order polymorphic typed lambda calculus.

The algorithm always says "yes".

I've wondered whether it might make an interesting "glue" language.
--
"conventional orthography is ... a near optimal system for the
lexical representation of English words." Chomsky & Halle, S.P.E.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/~ok; RMIT Comp.Sci.

Mon, 27 Jul 1998 03:00:00 GMT

 Page 1 of 3 [ 30 post ] Go to page: [1] [2] [3]

Relevant Pages