Author 
Message 
Amy Capl #1 / 30

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 


Mark Mei #2 / 30

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 selfreference 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 hereplease forgive me), then there exist alternate ways of causing selfreference 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 


Mark A Bigg #3 / 30

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 


Barry Margol #4 / 30

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 selfreference, 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 realworld 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) 8733126  Fax (617) 8736351

Mon, 20 Jul 1998 03:00:00 GMT 


William D Cling #5 / 30

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 selfreproducing program. William D Clinger

Tue, 21 Jul 1998 03:00:00 GMT 


Matthias Blu #6 / 30

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 selfinspecting 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, murecursive 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 mindboggingly 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 


Ilias Kastan #7 / 30

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 reuse 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 


Ilias Kastan #8 / 30

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 01 (rec. enumerable) set. The set computed by any (terminating!) algorithm is a Delta01 (recursive) set, by definition. H happens to be a "complete" Sigma01 set (it "encodes" all Sigma01 sets) and from this one shows H is not Delta01. That is the unsolvabili ty of the Halting Problem. One way to understand "complete": _any_ Sigma01 set can be obtained as the set of n's for which a certain Turing machine halts. In fact, this means they are 'semidecidable': 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 (Delta01) if and only if both the set and its complement are Sigma01. Again, this is much less innocent than it sounds! There is a lot of 'difference' between H and any given computable (i.e. Delta01) set R. This can be seen from the closure properties of Delta01 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 Delta01 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(k1) 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 Delta01, good old R sets themselves! Ilias

Thu, 23 Jul 1998 03:00:00 GMT 


Jake Donh #9 / 30

halting is weak?
Barry> think it's pretty well recognized that a halting program Barry> that worked for most realworld 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 


Ben Abrah #10 / 30

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 reuse > 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 


nweinin.. #11 / 30

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 reuse >> 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 


Antoun Kanawa #12 / 30

halting is weak?
: : Barry> think it's pretty well recognized that a halting program : Barry> that worked for most realworld 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 


Antoun Kanawa #13 / 30

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 


Ben Abrah #14 / 30

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 nonportable 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 


Richard A. O'Kee #15 / 30

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? Secondorder 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] 
