On 4/7/2012 10:34, Warp wrote:
> Darren New<dne### [at] sanrrcom>  wrote:
>> Turing machines can't calculate everything.
>
>    Are there (provably) solvable problems that cannot be calculated with a
> Turing machine?

Sure. The algorithm for translating a Turing machine program into a UTM 
tape. That's the idea. :-) It's an algorithm that humans can follow that 
turing machines cannot.

Here's another: Navigating traffic.

http://www.youtube.com/watch?v=peDy2st2XpQ

A TM can calculate an answer *isomorphic* to the answer of an arbitrary 
problem, but it can't solve the actual problem as stated. However, that's 
pretty much begging the question, since the purpose of Turing inventing his 
machine was to define the world "calculate."

-- 
Darren New, San Diego CA, USA (PST)
   "Oh no! We're out of code juice!"
   "Don't panic. There's beans and filters
    in the cabinet."

Post a reply to this message