Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

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.


Comment on Re^3: perl not omnipotent? let's see!
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
Node Status?
node history
Node Type: note [id://501879]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others surveying the Monastery: (6)
As of 2014-09-18 07:20 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (108 votes), past polls