Newsgroups: comp.lang.misc
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!uupsi!cmcl2!sbcs!eeserv1.ic.sunysb.edu!jallen
From: jallen@eeserv1.ic.sunysb.edu (Joseph Allen)
Subject: Re: Halting Problem Solved! Film at 11! (Was Re: definitions)
Message-ID: <1991May10.062839.24532@sbcs.sunysb.edu>
Sender: usenet@sbcs.sunysb.edu (Usenet poster)
Organization: State University of New York at Stony Brook
References: <17088@chaph.usc.edu> <truesdel.673477298@sun418> <17115@chaph.usc.edu>
Date: Fri, 10 May 91 06:28:39 GMT

In article <17115@chaph.usc.edu> jeenglis@alcor.usc.edu (Joe English) writes:
>truesdel@nas.nasa.gov (David A. Truesdell) writes:
>>jeenglis@alcor.usc.edu (Joe English) writes:
>The interesting question is not whether or not an editor
>will halt on all inputs.  Looking at the problem
>this way is like looking at Emacs as a finite state machine
>accepting the regular expression ".*^X^C".  What's interesting
>are questions like "If I invoke ESC-X towers-of-hanoi, will
>it finish?"

Yes, after 64 disks everything will finish  :-)

Actually, for real-time systems the halting problem gets to very weird.  For
examaple, in an OS, if user 1 runs towers of hanoi in gnu-emacs before user 2
finishes compiling gnu C, the os will finish because it ran out of swap space,
but if user 2 finishes first....

For some things the halting problem is important.  I seem to remember some
register allocation techniques in an optimizing compiler needed halting
analysis.
-- 
/*  jallen@ic.sunysb.edu  */     /* Amazing */     /* Joe Allen 129.49.12.74 */
int a[1817];main(z,p,q,r){for(p=80;q+p-80;p-=2*a[p])for(z=9;z--;)q=3&(r=time(0)
+r*57)/7,q=q?q-1?q-2?1-p%79?-1:0:p%79-77?1:0:p<1659?79:0:p>158?-79:0,q?!a[p+q*2
]?a[p+=a[p+=q]=q]=q:0:0;for(;q++-1817;)printf(q%79?"%c":"%c\n"," #"[!a[q-1]]);}