Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

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

by tilly (Archbishop)
on Oct 21, 2005 at 03:35 UTC ( [id://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?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://501879]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others taking refuge in the Monastery: (4)
As of 2024-04-24 22:46 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found