Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical

Re^3: perl not omnipotent? let's see!

by tilly (Archbishop)
on Oct 21, 2005 at 03:35 UTC ( #501879=note: print w/replies, xml ) Need Help??

in reply to Re^2: perl not omnipotent? let's see!
in thread perl not omnipotent? let's see!

Um, no.

Turing's Halting Problem is about the impossibility of writing a program that can figure out whether another program will or will not halt on given input.

The result that you're referring to is variously known as Church's thesis, the Church-Turing thesis, Turing's thesis and Church's conjecture. There are many minor variations, but they all boil down to, "Anything that can be computed, can be computed on a Turing machine." This statement is unproveable because "can be computed" is undefined. However it is generally accepted, and holds true for every reasonable definition of "computed" that anyone has been able to come up with.

Replies are listed 'Best First'.
Re^4: perl not omnipotent? let's see!
by spiritway (Vicar) on Oct 21, 2005 at 04:59 UTC

    You are correct... my mistake. I confused the "Turing Machine" reference with Turing's Halting Problem.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://501879]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (8)
As of 2018-06-20 14:05 GMT
Find Nodes?
    Voting Booth?
    Should cpanminus be part of the standard Perl release?

    Results (116 votes). Check out past polls.