On 4/11/2012 2:13, Warp wrote:
>    Why would pattern recognition or playing music be unsolvable in a TM?

Because a TM, by definition, has neither microphone nor speaker.

>    My original question was: Are there *provably solvable* (in the mathematical
> sense) problems that cannot be solved with a TM.

Given that "programmed on a TM" is the definition of "solvable", any answer 
would be begging the question.

> (If you can prove them to
> be solvable, then it kind of implies that you can present algorithms to
> solve them.)

Not necessarily. There are many non-constructive existence proofs. (I.e., 
there are many proofs of the form "this proves at least one X exists" 
without telling you how to find that X.)

>> If the problem is "I have a TM program and I want to know what to put on the
>> tape of my UTM to run it", you can't solve that with a turing machine. :-)
>
>    Is it a provably solvable problem? If yes, then why cannot it be solved
> with a TM?

Because the input to the problem can't be represented on a TM tape. If you 
encode the input for a TM tape so a TM can solve it, you've just done the work.

-- 
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