masticol@athos.rutgers.edu (Steve Masticola) (04/25/91)
Turing's proof of the undecidability of the halting problem is based on assuming that an algorithm to decide halting existed, and then proving from that a contradiction. This brings up my point: Is it possible to define an algorithm s.t. its termination is undecidable? (Since I like to play with computers more than I like to play with theories, I'll phrase the question in terms of a "program" rather than an "algorithm".) For 10 points: Give the source code for a sequential program (in the language of your choice) such that: * The program compiles correctly and executes without errors; * The program does not read any input or respond to any external signals; * It is undecidable whether the program terminates. - Steve (masticol@cs.rutgers.edu)
sethb@Morgan.COM (Seth Breidbart) (04/25/91)
In article <Apr.25.08.44.05.1991.23782@athos.rutgers.edu> masticol@athos.rutgers.edu (Steve Masticola) writes: : > Is it >possible to define an algorithm s.t. its termination is undecidable? > >For 10 points: > >Give the source code for a sequential program (in the language of your >choice) such that: > >* The program compiles correctly and executes without errors; >* The program does not read any input or respond to any external > signals; >* It is undecidable whether the program terminates. This clearly cannot be done. For any program that does not read input, consider the following two programs: Program 1: Print "The program halts." Program 2: Print "The program does not halt." One of those two correctly "decides" whether the given program halts. If you're asking whether there is a program that we don't know the termination behavior of, consider a program that searches for counterexamples to Fermat's Last Theorem (or your favorite open conjecture). Seth sethb@fid.morgan.com
rockwell@socrates.umd.edu (Raul Rockwell) (04/26/91)
Steve Masticola writes: > For 10 points: > Give the source code for a sequential program (in the language of > your choice) such that: > * The program compiles correctly and executes without errors; > * The program does not read any input or respond to any external > signals; > * It is undecidable whether the program terminates. Well I, for one, would rather describe such a program than write it: (1) Find a problem which is unprovable, except by example. (2) Write a program to find a solution by trial and error. (Just plod through all possible solutions, one at a time). Raul Rockwell
thomson@hub.toronto.edu (Brian Thomson) (04/26/91)
In article <Apr.25.08.44.05.1991.23782@athos.rutgers.edu> masticol@athos.rutgers.edu (Steve Masticola) writes: > >Turing's proof of the undecidability of the halting problem is based >on assuming that an algorithm to decide halting existed, and then >proving from that a contradiction. This brings up my point: Is it >possible to define an algorithm s.t. its termination is undecidable? >(Since I like to play with computers more than I like to play with >theories, I'll phrase the question in terms of a "program" rather than >an "algorithm".) > >For 10 points: > >Give the source code for a sequential program (in the language of your >choice) such that: > >* The program compiles correctly and executes without errors; >* The program does not read any input or respond to any external > signals; >* It is undecidable whether the program terminates. You are changing the rules in mid-stream. Why do you require that the program not read any input? The original problem did not have this constraint. -- Brian Thomson, CSRI Univ. of Toronto utcsri!uthub!thomson, thomson@hub.toronto.edu
matthew@cs.uq.oz.au (Matthew McDonald) (04/26/91)
In article <Apr.25.08.44.05.1991.23782@athos.rutgers.edu> masticol@athos.rutgers.edu (Steve Masticola) writes: > >Turing's proof of the undecidability of the halting problem is based >on assuming that an algorithm to decide halting existed, and then >proving from that a contradiction. This brings up my point: Is it >possible to define an algorithm s.t. its termination is undecidable? >(Since I like to play with computers more than I like to play with >theories, I'll phrase the question in terms of a "program" rather than >an "algorithm".) > >For 10 points: > >Give the source code for a sequential program (in the language of your >choice) such that: > >* The program compiles correctly and executes without errors; >* The program does not read any input or respond to any external > signals; >* It is undecidable whether the program terminates. > I don't know whether or not the termination of the following procedure is decidable, but I'll bet *you* can't decide anyway :-). void goldbach() { int i; int j, k; int found_it; for (i=2; ;i += 2) { found_it = 0; for (j = 1; j <= i && !found_it; j++) { for (k = 1; k <= i && !found_it; k++) if (prime(j) && prime(k) && j * k == i) found_it = 1; if (!found_it && k == j && j == i) /* Got even number that's not sum of 2 primes */ return; } } } Not a very theoretical answer but you "like to play with computers more than" you "like to play with theories" anyway. Do I get 5 points???? >- Steve (masticol@cs.rutgers.edu) Matthew.
gillies@m.cs.uiuc.edu (Don Gillies) (04/26/91)
masticol@athos.rutgers.edu (Steve Masticola) writes: >Give the source code for a sequential program (in the language of your >choice) such that: >* It is undecidable whether the program terminates. We pitiful humans are unable to build turing machines; nobody has ever constructed a computer that was more than a DFA, and nobody ever will (since all computers have a fixed amount of memory). So in a practical sense, no such program exists. --
lavinus@csgrad.cs.vt.edu (04/26/91)
Hi!
My personal favorite is the following:
proc foo(n)
while (n > 1)
if (even(n)) n = n div 2
else n = 3 * n + 1
end
As far as I know, it has never been proven that this program halts for all
n. Evidence to the contrary would be quite welcome (BTW, I believe the
credit for this problem is due to Ulam).
Joe
--
_________________________________ \ ___________________________________
Joseph W. Lavinus, Virginia Tech \ email: lavinus@csgrad.cs.vt.edu
1204-A University Terrace /\ phone: (703) 552-0241
Blacksburg, VA 24060 / \ (703) 231-5853kumarv@paul.rutgers.edu (kumar vadaparty) (04/26/91)
In article <Apr.25.08.44.05.1991.23782@athos.rutgers.edu>, masticol@athos.rutgers.edu (Steve Masticola) writes: > > Turing's proof of the undecidability of the halting problem is based > on assuming that an algorithm to decide halting existed, and then > proving from that a contradiction. This brings up my point: Is it > possible to define an algorithm s.t. its termination is undecidable? Sorry, but I am a bit confused. Typically, problems are undecidable. By problem they mean determining the membership of an object in a collection of objects satisfying a specific property (syntactic or semantic). Hence I am kind of confused about the meaning of "algorithm termination being undecidable". > Give the source code for a sequential program (in the language of your > choice) such that: > > * The program compiles correctly and executes without errors; > * The program does not read any input or respond to any external > signals; > * It is undecidable whether the program terminates. Again, you may have to re-phrase your problem. For something to be undecidable, we need a collection S and a question, "how hard is it to determine the membership of an arbitrary object in S?" One way, I can think of is: relax the second condition and say the program takes input. Then you may ask as follows: Give a program P of your choice language such that if S denotes the set of inputs on which the program P halts, then the problem of determining whether an arbitrary input belongs to this set S is undecidable (i.e. the set S is non-recursive). By making P to be a universal turing machine (with standard encodings), it is not difficult to show that the halting problem reduces to S and hence S is not recursive. > - Steve (masticol@cs.rutgers.edu) kumar. --
nielsen@procyon.crd.ge.com (paul e nielsen) (04/27/91)
In article <Apr.25.08.44.05.1991.23782@athos.rutgers.edu> masticol@athos.rutgers.edu (Steve Masticola) writes: > >Turing's proof of the undecidability of the halting problem is based >on assuming that an algorithm to decide halting existed, and then >proving from that a contradiction. This brings up my point: Is it >possible to define an algorithm s.t. its termination is undecidable? >(Since I like to play with computers more than I like to play with >theories, I'll phrase the question in terms of a "program" rather than >an "algorithm".) > >For 10 points: > >Give the source code for a sequential program (in the language of your >choice) such that: > >* The program compiles correctly and executes without errors; >* The program does not read any input or respond to any external > signals; >* It is undecidable whether the program terminates. > >- Steve (masticol@cs.rutgers.edu) Here's a short program you can play with at home, if you have Common Lisp. The decidability of its termination is based on proving Fermat's Last Theorem. (defun fermat () "Find a solution to Fermat's Last Theorem" (do ((a 1 (1+ a))) (NIL) ; Terminates when solution found (do ((b 1 (1+ b))) ((> b a)) ; Assume A >= B (do ((c a (1+ c))) ; C >= A && C >= B ((=> c (+ a b))) ; C < A + B (triangle ineq) (do ((i 2 (1+ i)) (prev NIL cur) (cur 0)) (NIL) ; Terminates when difference is increasing (cond ((zerop (setf cur (abs (- (expt c i) (+ (expt a i) (expt b i)))))) (return-from fermat ; Halt program! (format NIL "~D^~D + ~D^~D = ~D^~D" a i b i c i))) ((and prev (>= cur prev)) ; Difference increasing (return))) ; Return from innermost do ))))) P.S. Where can I redeem my 10 points? -- =============================================================================== Paul Nielsen VOICE: (518) 387-5141 GE Corporate R&D Center INET: nielsen@crd.ge.com Schenectady, NY 12345 UUCP: uunet!crd.ge.com!nielsen
mmcg@bruce.cs.monash.OZ.AU (Mike McGaughey) (04/27/91)
masticol@athos.rutgers.edu (Steve Masticola) writes: >proving from that a contradiction. This brings up my point: Is it >possible to define an algorithm s.t. its termination is undecidable? Yes. Pick any famous unsolved mathematical theorem, and try to solve it by brute force - i.e. prove that this one terminates: read x while (x > 1) if x mod 2 = 0 then x = x / 2 else x = 3 * x + 1 You'll have a lot of fun with that one :). >* The program compiles correctly and executes without errors; >* The program does not read any input or respond to any external > signals; >* It is undecidable whether the program terminates. Oh, no input. How about a program to find a counterexample to Fermat's last theorem then? Mike. -- Mike McGaughey AARNET: mmcg@bruce.cs.monash.oz.au "His state is kingly; thousands at his bidding speed, And post o'er land and ocean without rest." - Milton.
bremner@fornax.UUCP (David Bremner) (04/27/91)
I hate to be a wet blanket, but the fact that we do not have a proof of Fermat's last "theorem" does not actually prove that such a proof does not exist. Unless I missed something important... -- -------- bremner@cs.sfu.ca ubc-cs!fornax!bremner
peyote@coredump.umiacs.umd.edu (Gary Flake) (04/27/91)
I'll give this a try.
One assumption: I get a floating point representaion such that the
mantissa grows as needed for precision, not to exceed linear growth,
so a TM can handle this as well.
logistic_map()
{
float start = 0.72683747835872456784398234476582;
float end = 0.38947584759487534985798237949835;
while (start != end)
start = 3.9 * start * (1.0 - start);
}
As a discrete chaotic system, the above will *probably* not
repeat itself, but the point is that you can't know without
running the beast. Why the 3.9 (instead of 4.0) ? Ulam
came up with an analytical solution for 4.0, so I thought
that we'd add some more ugliness to the function. 3.9 is
still within the chaotic regime.
Extra credit for brevity?
Gary Flake.
------
peyote@umiacs.umd.eduian@oravax.UUCP (Ian Sutherland) (04/27/91)
In article <Apr.25.08.44.05.1991.23782@athos.rutgers.edu> masticol@athos.rutgers.edu (Steve Masticola) writes: > >This brings up my point: Is it >possible to define an algorithm s.t. its termination is undecidable? What do you mean by the termination of a single program being "undecidable"? The halting problem is recursively undecidable in the sense that there is no recursive function which, given a program (which takes no arguments), tells you whether the program halts or not. The termination of a single program P can't be undecidable in this sense, because there's definitely a recursive function of no arguments which tells you whether P halts or not. You may not know what it is, but it exists (no philosophical arguments please). -- Ian Sutherland ian@cambridge.oracorp.com Sans peur
rockwell@socrates.umd.edu (Raul Rockwell) (04/28/91)
Don Gillies > Steve Masticola >| >|Give the source code for a sequential program (in the language of your >|choice) such that: >|* It is undecidable whether the program terminates. > We pitiful humans are unable to build turing machines; nobody has > ever constructed a computer that was more than a DFA, and nobody > ever will (since all computers have a fixed amount of memory). > So in a practical sense, no such program exists. I've been wondering if someone would bring this up. However, it is not true that all computers have a fixed amount of memory. A number of machines have been designed such that you can add memory even while the computer is running. Also, note that a program can be suspended temporarily and loaded onto a bigger and better machine without actually terminating the program. So it seems to me you could continue a computation until some disaster strikes and wrecks your system. Disaster is a rather odd method of terminating execution: in this sense all programs can be considered to halt. However this says nothing about the computation, and instead is a statement about the implementation of the platform (or perhaps about the physical universe). Raul Rockwell
ian@oravax.UUCP (Ian Sutherland) (04/29/91)
If what we're after is programs whose halting is difficult to prove, how about a program that searchs for a proof of "A & ~A" from the axioms of ZFC? If it doesn't halt, we can't prove in ZFC that it doesn't. We have reason to believe, however, that any obvious proof that this program halts would have been found a while back. -- Ian Sutherland ian@cambridge.oracorp.com Sans peur
hbe@sonia.math.ucla.edu (H. Enderton) (04/29/91)
Ian Sutherland has made an interesting point. On the one hand, for a particular (fixed) Turing machine and a particular (fixed) input, the *truth* of its halting does not qualify as a "decision problem"--either it does or it doesn't. On the other hand, the *provability* of its halting can be an interesting question. For a related example, take Rado's sigma function (in the Busy Beaver problem). This grows faster than any recursive function. Sure, there is some machine that can write sigma(5) on its output tape. But would we know that *that* was what it had done? Only if we can prove an equation "sigma(5) = xxx" (where xxx is the right answer, whatever it is). And (under reasonable assumptions) we can prove in ZFC equations of the form "sigma(m)=n" for only finitely many m's. And it may well be that m = 5 is not one of them. Moral: It's one thing to know that a Turing machine *exists* that has the answers you seek; it's quite another to know what that machine is.
dww@math.fu-berlin.de (Debora Weber-Wulff) (04/30/91)
lavinus@csgrad.cs.vt.edu writes: > >My personal favorite is the following: > >proc foo(n) > while (n > 1) > if (even(n)) n = n div 2 > else n = 3 * n + 1 >end > >As far as I know, it has never been proven that this program halts for all >n. Evidence to the contrary would be quite welcome (BTW, I believe the >credit for this problem is due to Ulam). In Germany, we learn that the "Rollercoaster Function" (Achterbahn- funktion) is due to the famous (German!) Mathematician Collatz. -- Debora Weber-Wulff snail: FU Berlin, ZI Fachdidaktiken, Habelschwerdter Allee 45, W-1000 Berlin 33 email: weberwu@inf.fu-berlin.de, dww@math.fu-berlin.de
sethb@Morgan.COM (Seth Breidbart) (04/30/91)
In article <Apr.25.08.44.05.1991.23782@athos.rutgers.edu> masticol@athos.rutgers.edu (Steve Masticola) writes: >Turing's proof of the undecidability of the halting problem is based >on assuming that an algorithm to decide halting existed, and then >proving from that a contradiction. This brings up my point: Is it >possible to define an algorithm s.t. its termination is undecidable? >(Since I like to play with computers more than I like to play with >theories, I'll phrase the question in terms of a "program" rather than >an "algorithm".) > >For 10 points: > >Give the source code for a sequential program (in the language of your >choice) such that: > >* The program compiles correctly and executes without errors; >* The program does not read any input or respond to any external > signals; >* It is undecidable whether the program terminates. In a previous posting, I pointed out that any such program can be "decided", where "decided" has the usual meaning (="the correct answer is given"). Since the answer is either "halts" or "does not halt", then there is a trivial program to "decide". I can't necessarily specify the program, but I can give you two programs, and guarantee that one of them "decides". If "decide" is taken to mean "prove, in a formal system", then the answer changes. Goedel proved that in any sufficiently powerful formal system there are true but unprovable statements. Consider a program that searches for a proof or counterexample to one of these. If we prove it halts, then either the statement is false or it is provable; but we know that it's true and unprovable. If we prove that it doesn't halt, then we've proven the lack of a counterexample, therefore we've proven the statement, which we can't do (in that formal system). An interesting example of such an unprovable assertion is: "The complexity of the string xxxx...xxx is greater than the number of bits in it", where the string xxxx...xxx is longer than a description of the formal system, and random. See Chaitin's work for a proof that for any formal system, there is a maximal provable complexity (the complexity of a string is defined as the length of the shortest program that outputs that string), and that length corresponds to the size of a description of the formal system. Seth sethb@fid.morgan.com
sethb@Morgan.COM (Seth Breidbart) (04/30/91)
In article <1991Apr26.135918.8607@m.cs.uiuc.edu> gillies@m.cs.uiuc.edu (Don Gillies) writes: >We pitiful humans are unable to build turing machines; nobody has ever >constructed a computer that was more than a DFA, and nobody ever will >(since all computers have a fixed amount of memory). A Turing Machine need not start with an infinite amount of memory. If I endow a foundation to add 1 tape square every year, then the memory is eventually large enough, and a Turing Machine results. In fact, if we consider USENET to be a single machine (why not?), and assume it to be constantly growing, then it fits the definition. Seth sethb@fid.morgan.com
turpin@cs.utexas.edu (Russell Turpin) (04/30/91)
----- In article <1991Apr29.154023.18594@math.ucla.edu> hbe@math.ucla.edu (H. Enderton) writes: > Ian Sutherland has made an interesting point. On the one hand, for a > particular (fixed) Turing machine and a particular (fixed) input, the > *truth* of its halting does not qualify as a "decision problem"--either > it does or it doesn't. On the other hand, the *provability* of its > halting can be an interesting question. ... I have found that the terminology involved also confuses some people. In logic, one calls a theory undecidable if there is a proposition P such that neither P nor ~P is provable in the theory. By extension, such a sentence is sometimes said to be undecidable in the concerned theory. Thus, there is a natural kind of question many students ask: Might Fermat's Last Theorem (or some other proposition) be undecidable in first-order arithmetic (or whatever theory is concerned)? If this question is asked of someone whose natural framework is complexity theory, where decidability refers to a problem class, the answer is: of course it is decidable, because it only has one problem instance. In this framework, people don't refer to propositions as decidable or not, but rather as provable or not. The confusion is compounded because there are undecidable (sense 1) propositions in a theory iff the question of whether an arbitrary proposition is provable in a theory is is undecidable (sense 2). I know, this is not any great issue, it is just a matter of terminology. I thought it was worth mentioning only because I have seen people confused over it on several occasions. Russell
jgk@osc.COM (Joe Keane) (05/01/91)
In article <Apr.25.08.44.05.1991.23782@athos.rutgers.edu> masticol@athos.rutgers.edu (Steve Masticola) writes: >Give the source code for a sequential program (in the language of your >choice) such that: > >* The program compiles correctly and executes without errors; >* The program does not read any input or respond to any external > signals; >* It is undecidable whether the program terminates. > >- Steve (masticol@cs.rutgers.edu) This doesn't make sense, although it is a common mistake. Given a program which takes no input, either it halts or it doesn't. In either case, the program is trivially decidable. A common example of such a program is one which halts if and only if there's a counter-example to Fermat's last theorem. While we don't know at present whether or not it will halt, it's still considered decidable. Now if say we take the exponent as input, then maybe it's undecidable, but i doubt it. For a function to be undecidable, it must have some input parameter which changes the behavior of the program in some complicated way. We can be more specific than `complicated' and say that the way it changes the behavior can't be determined in all cases by any given algorithm. A good example of an undecidable program is a Turing machine simulator. Assume it reads some description of a Turing machine from its input, and then runs the machine and halts if it does. If the simulator is itself a Turing machine, then we have the case of a universal Turing machine. -- Joe Keane, amateur mathematician jgk@osc.com (...!uunet!stratus!osc!jgk)
jono@dec06.cs.monash.edu.au (Jonathan Oliver) (05/01/91)
In <3132@ylum.Morgan.COM> sethb@Morgan.COM (Seth Breidbart) writes: >>We pitiful humans are unable to build turing machines; nobody has ever >>constructed a computer that was more than a DFA, and nobody ever will >>(since all computers have a fixed amount of memory). >A Turing Machine need not start with an infinite amount of memory. If >I endow a foundation to add 1 tape square every year, then the memory >is eventually large enough, and a Turing Machine results. >In fact, if we consider USENET to be a single machine (why not?), and >assume it to be constantly growing, then it fits the definition. >Seth sethb@fid.morgan.com There is indeed an upper limit on the amount of memory a computer can have, since the universe is finite (approx 10^70 electrons from memory). Jon Oliver
rockwell@socrates.umd.edu (Raul Rockwell) (05/01/91)
Jonathan Oliver writes: [ on Seth Breidbart's observation that computers have limited memory] > There is indeed an upper limit on the amount of memory a computer > can have, since the universe is finite (approx 10^70 electrons from > memory). Ah, yes. Theoretically ;-) Since we're not even close to that limit, may I suggest that perhaps it has not yet been measured accurately? A couple possibilities which are expressible about current physics: (1) What if the "big bang" was a "local" event in some larger region of space? That it's big does not mean that there is nothing bigger. (2) What if conservation of energy is "merely a statistical phenomena". Note that the wonderful thing about conservation is that it makes math a hell of a lot easier. That's a good reason for using it, but not a good reason for believing it. (How could you even test for violations of conservation of energy? What's the difference between energy arriving from elsewhere and "created energy" [whatever that is]?). Anyways, infinity describes a condition where for any number picked, you can pick yet another which is bigger -- an awfully silly idea, on the face of it, but awfully silly nonetheless ;-) Raul Rockwell
kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell) (05/01/91)
In article <jono.673068358@dec06> jono@dec06.cs.monash.edu.au (Jonathan Oliver) writes: >There is indeed an upper limit on the amount of memory a computer can have, >since the universe is finite (approx 10^70 electrons from memory). The current ``popular'' success of the BB aside, I don't know that the finiteness of the (material?) universe has been proved. In any case here are some other outs -- (a) why use electrons? Maybe there is some class of thingy around here somewhere of which there _are_ an unbounded number. Since it _has_ been shown the lower bound on energy required for computation is zero (i.e. it can continue after any ``heat death'') we don't even require that thingy to have energy associated with it -- merely to be detectable (and I don't know how to detect something with zero rest energy, so don't ask :-). (b) The amount of information is not limited to the number of particles; but the number of energy states they can collectively access. A free particle can access an infinite number of states. If we consider the universe to be a closed system then collectively it is a set of free particles and can access an infinite number of energy levels (states). (There are obviously quite a few deep philosophical problems/questions here). (c) Various interpretations of QP may indicate info can be stored ``between the cracks'', so to speak :-) :-) Reality may know no limits. ;^) -kym
fs@caesar.cs.tulane.edu (Frank Silbermann) (05/01/91)
>>> We are unable to build Turing machines; >>> nobody has ever constructed a computer that was >>> more than a DFA, and nobody ever will >>> (since all computers have a fixed amount of memory). >> If I endow a foundation to add 1 tape square every year, >> then the memory is eventually large enough, and a Turing Machine >> results. > There is an upper limit on the amount of memory a computer can have, > since the universe is finite. All of you miss the point. The Turing machine _model_ is a technique to abstract out the size of the memory from the machine description. A Turing machine may be thought of as a finite automaton SCHEMA. Each time you bound a TM's tape length, the result is a new FA. By instantiating the TM to FA's with increasing tape length, you generate a series of increasingly powerful finite automata. In terms of denotational semantics, for any such FA schema (i.e. TM), the shorter-tape FA's approximate the larger-tape FA's. The least upper bound (limit) of this chain of finite automata is the conceptual (not physical) Turing machine. Turing decidability means that there exists a finite automaton _schema_ for which some sufficiently large instantiation decides the problem. (this is related to Denotational Semantics's idea of continuity). Turing undecidablity means that we _cannot_ solve the problem by building successively larger finite automata generated from such a schema. This high-level insight is often valuable. Frank Silbermann fs@cs.tulane.edu Tulane University New Orleans, Louisiana USA
unx20491@unx2.ucc.okstate.edu (Inscrutable Eric) (05/03/91)
In article <18974@crdgw1.crd.ge.com> nielsen@procyon.crd.ge.com (paul e nielsen) writes: >In article <Apr.25.08.44.05.1991.23782@athos.rutgers.edu> masticol@athos.rutgers.edu (Steve Masticola) writes: >> >> [Delete, delete, delete, ...] >>Give the source code for a sequential program (in the language of your >>choice) such that: >> >>* The program compiles correctly and executes without errors; > >(defun fermat () > "Find a solution to Fermat's Last Theorem" > (do ((a 1 (1+ a))) > (NIL) ; Terminates when solution found > [Delete, delete, delete, ...] I'll bet that there is no computer in the world that will execute this code without returning an error when a, or any other of the variables, exceeds the computer's MaxInt. Seems like a silly point, but this code doesn't seem to follow all of the rules. For example, it probably won't execute without errors. >P.S. Where can I redeem my 10 points? Nowhere, your code fails to comply with all of the rules for such code. ----------------------------------------------------------------------------- "I call myself `'d' Kidd,' because no one else will." unx20491@unx2.ucc.okstate.edu (Eric Gindrup) God created a countable infinity of numbers. All else is the work of consistent people. "Consistency is the hobgoblin of little minds."
fs@caesar.cs.tulane.edu (Frank Silbermann) (05/03/91)
We have concluded that the halting problem is decidable for any specific input-free program P. Proof: Consider algorithms A & B such that algorithm A reads in a program and returns YES; algorithm B reads in a program and returns NO. One of these algorithms solves the halting problem for P. Is there any program P for which it has been proven that we can never know which of these two algorithms, A and B, is the right one? Frank Silbermann fs@cs.tulane.edu Tulane University New Orleans, Louisiana USA
nielsen@procyon.crd.ge.com (paul e nielsen) (05/03/91)
In article <1991May2.190138.15254@unx2.ucc.okstate.edu> unx20491@unx2.ucc.okstate.edu (Inscrutable Eric) writes: >I'll bet that there is no computer in the world that will execute this >code without returning an error when a, or any other of the variables, >exceeds the computer's MaxInt. Seems like a silly point, but this code >doesn't seem to follow all of the rules. For example, it probably won't >execute without errors. >>P.S. Where can I redeem my 10 points? >Nowhere, your code fails to comply with all of the rules for such code. Interesting point for most computer languages, but Lisp has bignums. "Unlike most programming languages, Common Lisp in principle imposes no limit on the magnitude of an integer; storage is automatically allocated as necessary to represent large integers." (CLtL 2nd ed, p.16) Thus the upper bound on the size of an integer is limited by the size of the computer's total memory, rather than the word size or some MaxInt. Of course total memory is assumed to be infinite. -- =============================================================================== Paul Nielsen VOICE: (518) 387-5141 GE Corporate R&D Center INET: nielsen@crd.ge.com Schenectady, NY 12345 UUCP: uunet!crd.ge.com!nielsen
sethb@Morgan.COM (Seth Breidbart) (05/03/91)
In article <7277@rex.cs.tulane.edu> fs@caesar.cs.tulane.edu (Frank Silbermann) asks: >We have concluded that the halting problem >is decidable for any specific input-free program P. > >Proof: >Consider algorithms A & B such that >algorithm A reads in a program and returns YES; >algorithm B reads in a program and returns NO. >One of these algorithms solves the halting problem for P. > >Is there any program P for which it has been proven that >we can never know which of these two algorithms, A and B, >is the right one? It depends on what you mean by "proven". If you specify the formal system in advance, then I can construct such a machine: Pick a random string whose length is longer than the description of the system. Set a machine to testing whether that string is random, to halt if it determines that the string is not random, to loop forever if it cannot so determine. Since, in any formal system, there is an upper limit to the length of any string that can be proven random, this machine will not halt. But a proof that it will not halt is a proof that the string is random. "Random" is used in the algorithmic sense, as described by Chaitin. On the other hand, the answer is "no". If the machine will halt, then that can obviously be proven. If it will not halt, then add as an axiom "that machine does not halt". The new system is consistent, and the non-halting of the machine is easy to prove in that system. In fact, we see that if the halting of the machine is unprovable, it cannot halt. Seth sethb@fid.morgan.com
man7421@csd4.csd.uwm.edu (Francis Man) (05/03/91)
Get yourself to the library and look for the book COMPUTABILITY, COMPLEXITY, AND LANGUAGES FUNDAMENTALS OF THEORETICAL COMPUTER SCIENCE BY MARTIN D. DAVIS AND ELAINE J. WEYUKER QA 267.D38 1983 ISBN 0-12-206380-5 You will find the algorithm of the program for your homework!!!
raymond@cs.ruu.nl (Raymond Hoofman) (05/03/91)
In <7277@rex.cs.tulane.edu> fs@caesar.cs.tulane.edu (Frank Silbermann) writes: >We have concluded that the halting problem >is decidable for any specific input-free program P. > >Proof: >Consider algorithms A & B such that >algorithm A reads in a program and returns YES; >algorithm B reads in a program and returns NO. >One of these algorithms solves the halting problem for P. > >Is there any program P for which it has been proven that >we can never know which of these two algorithms, A and B, >is the right one? It is not possible to prove such a statement about a program P. Suppose P is a program for which it has been proven that we can never know which of these algorithms, A and B, is the right one. Now let P run on a computer. If P halts, say after n units of time, then we know after n units of time that A solves the halting problem for P. Because this is in contradiction with our assumption about P, we must conclude that P does not halt. Hence the existence of a proof of the fact that we can never know which of A,B decides P, implies the fact that P does not terminate, and hence it implies the fact that B decides P. Contradiction. -- ---------------------------------------------------------------------------- | Raymond Hoofman | "Love without pain is like | | raymond@cs.ruu.nl | pain without love." | ----------------------------------------------------------------------------
petry@milton.u.washington.edu (David Petry) (05/04/91)
In article <4760@osc.COM> jgk@osc.UUCP (Joe Keane) writes: > > Given a program >which takes no input, either it halts or it doesn't. Am I the only one that questions the validity of the above assertion? It seems reasonable to me to say, for example, that any program must either halt within one million steps, or not halt within one million steps. But without some explicit bound, the statement seems to be without meaning. David Petry
callahan@cs.jhu.edu (Paul Callahan) (05/04/91)
In article <1991May3.185947.19929@milton.u.washington.edu> petry@milton.u.washington.edu (David Petry) writes: >In article <4760@osc.COM> jgk@osc.UUCP (Joe Keane) writes: >> >> Given a program >>which takes no input, either it halts or it doesn't. > >Am I the only one that questions the validity of the above assertion? > >It seems reasonable to me to say, for example, that any program must either >halt within one million steps, or not halt within one million steps. But >without some explicit bound, the statement seems to be without meaning. Well, what's wrong with saying "There exists some explicit bound n, such that program P halts in n steps." To say that a program halts implies an existential quantification over all positive integers, and this is completely well defined. In fact, a statement to the effect that "program P halts" is clearly verifiable if it is true (which is why the set of halting programs is recursively enumerable). I don't see any problem at all. -- Paul Callahan callahan@cs.jhu.edu
jgk@osc.COM (Joe Keane) (05/08/91)
In article <4760@osc.COM> jgk@osc.UUCP i write: >Given a program which takes no input, either it halts or it doesn't. In article <1991May3.185947.19929@milton.u.washington.edu> petry@milton.u.washington.edu (David Petry) writes: >Am I the only one that questions the validity of the above assertion? I have to admit i have a certain intuitive uneasiness about assertions like this. Logically, it's simply the law of the excluded middle. However, it may be that neither alternative is provable. In computer science, we would say that you need an oracle to decide the answer. In mathematics, you just use the Axiom of Choice to eliminate the problem. This affirms my opinion that a lot of mathematicians don't understand what's going on. Constructivist mathematicians are of course excluded from the previous comment. -- Joe Keane, amateur mathematician jgk@osc.com (...!uunet!stratus!osc!jgk)
traff@ecrc.de (Jesper Larsson Traff) (05/10/91)
In article <1991May1.072918.844@bingvaxu.cc.binghamton.edu>, kym@bingvaxu.cc.binghamton.edu (R. Kym Horsell) writes: |>In article <jono.673068358@dec06> jono@dec06.cs.monash.edu.au (Jonathan Oliver) writes: |> |>(a) why use electrons? Maybe there is some class of thingy around here |> somewhere of which there _are_ an unbounded number. Since it |> _has_ been shown the lower bound on energy required for |> computation is zero (i.e. it can continue after any ``heat |> death'') we don't even require that thingy to have energy That's an interesting remark. Can you give a pointer as to where this lower bound is given. Sorry for my ignorance. Jesper Larsson Traff, traff@ecrc.de ECRC - European Computer-Industry Research Centre - Mu:nchen, Deutschland
callahan@cs.jhu.edu (Paul Callahan) (05/10/91)
In article <4765@osc.COM> jgk@osc.COM (Joe Keane) writes: >In article <4760@osc.COM> jgk@osc.UUCP i write: >>Given a program which takes no input, either it halts or it doesn't. > >In article <1991May3.185947.19929@milton.u.washington.edu> >petry@milton.u.washington.edu (David Petry) writes: >>Am I the only one that questions the validity of the above assertion? > >I have to admit i have a certain intuitive uneasiness about assertions like >this. Logically, it's simply the law of the excluded middle. However, it may >be that neither alternative is provable. Wrong. The assertion "program X halts" is provable if and only if it is true. For a proof, we simply exhibit a correct trace of the execution up to step n, the point at which it halts. The assertion "program X does not halt" may not have a proof, but it is simply incorrect to suggest that "neither alternative is provable." This is what it means to say that the set of halting programs is recursively enumerable (though not recursive). -- Paul Callahan callahan@cs.jhu.edu