Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!olivea!uunet!munnari.oz.au!bruce!mmcg From: mmcg@bruce.cs.monash.OZ.AU (Mike McGaughey) Newsgroups: comp.theory Subject: Re: Question on halting problem Keywords: for 10 bonus points... Message-ID: <4026@bruce.cs.monash.OZ.AU> Date: 26 Apr 91 22:27:41 GMT References: Organization: Monash Uni. Computer Science, Australia Lines: 31 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.