Here's an interesting thought:

There is no Turing machine capable of translating a Turing machine program 
into an input tape for a Universal Turing Machine.

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

Em 05/04/2012 23:56, Darren New escreveu:
> Here's an interesting thought:
>
> There is no Turing machine capable of translating a Turing machine
> program into an input tape for a Universal Turing Machine.

LOLWUT?

gotta sleep...

Post a reply to this message

On 06/04/2012 03:56 AM, Darren New wrote:
> Here's an interesting thought:
>
> There is no Turing machine capable of translating a Turing machine
> program into an input tape for a Universal Turing Machine.

Turning machines only take tapes as input. To convert a Turning machine 
into a tape, it would /already/ have to be a tape so it could be input. :-P

Post a reply to this message

Orchid Win7 v1 <voi### [at] devnull> wrote:
> Turning machines only take tapes as input. To convert a Turning machine 
> into a tape, it would /already/ have to be a tape so it could be input. :-P

  What's a turning machine?

-- 
                                                          - Warp

Post a reply to this message

>    What's a turning machine?

My keyboard hates me. Possibly since I broke it out if frustration when 
I failed Assassin's Creed for the 25th time because the damned jump 
button WOULD NOT respond to my violent repeated pressing...

Post a reply to this message

On 4/5/2012 7:56 PM, Darren New wrote:
> Here's an interesting thought:
>
> There is no Turing machine capable of translating a Turing machine
> program into an input tape for a Universal Turing Machine.
>

Could you be more specific?  There's multiple ways to interpret what you 
mean and some of these interpretations are true while others are false.

Post a reply to this message

On Fri, 06 Apr 2012 05:24:40 -0400, Warp wrote:

> Orchid Win7 v1 <voi### [at] devnull> wrote:
>> Turning machines only take tapes as input. To convert a Turning machine
>> into a tape, it would /already/ have to be a tape so it could be input.
>> :-P
> 
>   What's a turning machine?

A steering wheel.

Jim

Post a reply to this message

On 4/6/2012 2:12, Orchid Win7 v1 wrote:
> On 06/04/2012 03:56 AM, Darren New wrote:
>> Here's an interesting thought:
>>
>> There is no Turing machine capable of translating a Turing machine
>> program into an input tape for a Universal Turing Machine.
>
> Turning machines only take tapes as input. To convert a Turning machine into
> a tape, it would /already/ have to be a tape so it could be input. :-P

Ding ding ding! Exactly. That's why real computers can do things that Turing 
machines can't, for example.  Turing machines can't calculate everything. 
They can do calculations isomorphic to any calculation.

(Assuming you define "calculation" correctly.)

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

On 4/6/2012 8:14, Kevin Wampler wrote:
> On 4/5/2012 7:56 PM, Darren New wrote:
>> Here's an interesting thought:
>>
>> There is no Turing machine capable of translating a Turing machine
>> program into an input tape for a Universal Turing Machine.
>>
>
> Could you be more specific? There's multiple ways to interpret what you mean
> and some of these interpretations are true while others are false.

A turing machine program is a tuple, one element of which is a set of 
tuples. Turing machines don't work with sets of tuples. I.e., exactly what 
Andrew said.

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

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?

-- 
                                                          - Warp

Post a reply to this message

On 4/7/2012 10:28 AM, Darren New wrote:
>
> That's why real computers can do things that
> Turing machines can't

Consider both Turing machines and "real" computers require very similar 
encoding of a problem in order for a computation to be performed, what 
are you viewing as the critical distinction between them?  After all 
both essentially represent a problem as a string of symbols from an 
alphabet.

Real computers can, of course, interact with the physical world in a way 
that a TM can't, but I imagine that's not your point since it's a little 
like commenting that there's no mathematical algorithm which returns a 
sandwich as the result of it's computation.

Post a reply to this message

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

On 4/7/2012 14:17, Kevin Wampler wrote:
> require very similar encoding of a problem

I disagree that the encodings are similar.

> in order for a computation to be performed, what are
> you viewing as the critical distinction between them? After all both
> essentially represent a problem as a string of symbols from an alphabet.

Take, for example, quantum computers, for which this is untrue.

> Real computers can, of course, interact with the physical world in a way
> that a TM can't, but I imagine that's not your point since it's a little
> like commenting that there's no mathematical algorithm which returns a
> sandwich as the result of it's computation.

That too.

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

On 4/7/2012 3:06 PM, Darren New wrote:
> On 4/7/2012 14:17, Kevin Wampler wrote:
>> require very similar encoding of a problem
>
> I disagree that the encodings are similar.
>
>> in order for a computation to be performed, what are
>> you viewing as the critical distinction between them? After all both
>> essentially represent a problem as a string of symbols from an alphabet.
>
> Take, for example, quantum computers, for which this is untrue.
>

I was thinking more of existing computers, but you make a fair point.  I 
still find the definition of "calculation" you're implicitly using a 
pretty strange though, but to each their own.

Post a reply to this message

On 4/8/2012 9:16, Kevin Wampler wrote:
> On 4/7/2012 3:06 PM, Darren New wrote:
>> On 4/7/2012 14:17, Kevin Wampler wrote:
>>> require very similar encoding of a problem
>>
>> I disagree that the encodings are similar.
>>
>>> in order for a computation to be performed, what are
>>> you viewing as the critical distinction between them? After all both
>>> essentially represent a problem as a string of symbols from an alphabet.
>>
>> Take, for example, quantum computers, for which this is untrue.
>>
>
> I was thinking more of existing computers, but you make a fair point.

Well, the encoding in a real computer consists of varying levels of 
electrons, movements of electrons, and/or positions of magnetic moments. In 
a Turing machine, they're symbols. Real computers are analog.

> still find the definition of "calculation" you're implicitly using a pretty
> strange though, but to each their own.

Well, Turing machines were intended to offer a definition of computability. 
So clearly Turing himself thought anything isomorphic to a computation also 
counted as a computation. I just found it amusing that there re things we 
have our computers do every day that a Turing machine can't do, including 
programming universal turing machines.

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

Darren New <dne### [at] sanrrcom> wrote:
> A TM can calculate an answer *isomorphic* to the answer of an arbitrary 
> problem, but it can't solve the actual problem as stated.

  I don't really understand what the difference is.

  The only isomorphism I'm familiar with is graph isomorphism, and there
it's one of the strictest forms of graph equality. (Not only do isomorphic
graphs define the same language, but they are geometrically identical,
in other words they have the same amount of nodes and arcs, and there's
a one-to-one mapping between each one of them; if the nodes and/or arcs
are named, the names have to also correspond in the mapping.)

  It's hard to get any closer to identical than that.

-- 
                                                          - Warp

Post a reply to this message

On 4/8/2012 11:50, Warp wrote:
> Darren New<dne### [at] sanrrcom>  wrote:
>> A TM can calculate an answer *isomorphic* to the answer of an arbitrary
>> problem, but it can't solve the actual problem as stated.
>
>    I don't really understand what the difference is.
>
>    The only isomorphism I'm familiar with is graph isomorphism,

"isomorphic" means there's a one-to-one mapping from one thing to another 
thing. But that doesn't make them the same. It just means there's a mapping.

So a WAV file might be isomorphic to the position of the speaker at each 
given sample, but that doesn't mean a WAV file is an actual sound. It can be 
mapped to an actual sound.

A Turing machine can decompress a representation of an MP3 file into a 
representation of where the speaker would be at each given moment, but it 
can't actually play the music.

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

On 4/8/2012 11:25 AM, Darren New wrote:
> I just found it amusing
> that there re things we have our computers do every day that a Turing
> machine can't do, including programming universal turing machines.

I think perhaps this is the crux of the difference in out viewpoints.  I 
don't consider a "normal" computer as any more capable of programming a 
UTM in the sense you seem to mean it than a normal TM is.  Both have to 
operate on some encoding of the TM that the initial program is for, and 
I don't see why binary digits represented by electrical means are any 
less of an encoding than abstract symbols on a tape.

Post a reply to this message

On 4/8/2012 19:15, Kevin Wampler wrote:
> I think perhaps this is the crux of the difference in out viewpoints. I
> don't consider a "normal" computer as any more capable of programming a UTM
> in the sense you seem to mean it than a normal TM is.

A TM can't encode any sort of tape for any other TM.

> Both have to operate
> on some encoding of the TM that the initial program is for, and I don't see
> why binary digits represented by electrical means are any less of an
> encoding than abstract symbols on a tape.

We're confusing two things here. One is that real computers can perform 
computations that TMs can't, because TM's don't have cameras, microphones, 
etc. One TM can't program another TM at all, because a TM can only write to 
its own tape.

The other point is that humans can do things computers can't because we're 
capable of encoding things directly from reality with our inputs. (E.g., we 
can look at a hand-written representation of a turing machine program and 
mentally turn it into an actual turing machine program without outside 
assistance.)

I just found it amusing that programming a Universal Turing Machine is one 
thing a Universal Turing Machine can't do without assistance.

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

Darren New <dne### [at] sanrrcom> wrote:
> A Turing machine can decompress a representation of an MP3 file into a 
> representation of where the speaker would be at each given moment, but it 
> can't actually play the music.

  I don't understand what that has to do with solving a problem. It sounds
to me like you are using a fallacy of equivocation.

-- 
                                                          - Warp

Post a reply to this message

Em 09/04/2012 02:39, Darren New escreveu:
> We're confusing two things here. One is that real computers can perform
> computations that TMs can't, because TM's don't have cameras,
> microphones, etc.

Those are still tapes, minus time.  If you recorded all user input from 
any device and fed it to a TM, it'd still work the same.  Interaction 
means the TM waiting for more tape...

> One TM can't program another TM at all, because a TM
> can only write to its own tape.

I'm not sure I'm following, but this actually reminded me of programs 
that output their own source code.  And virus...

Post a reply to this message

On 4/9/2012 1:12, Warp wrote:
> Darren New<dne### [at] sanrrcom>  wrote:
>> A Turing machine can decompress a representation of an MP3 file into a
>> representation of where the speaker would be at each given moment, but it
>> can't actually play the music.
>
>    I don't understand what that has to do with solving a problem. It sounds
> to me like you are using a fallacy of equivocation.

If the problem is "I want to know what song this is" or "I want to listen to 
some music", then you haven't really solved the problem.

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. :-)

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

On 4/9/2012 21:14, nemesis wrote:
> Em 09/04/2012 02:39, Darren New escreveu:
>> We're confusing two things here. One is that real computers can perform
>> computations that TMs can't, because TM's don't have cameras,
>> microphones, etc.
>
> Those are still tapes, minus time.

No, they're really not. They're (possibly) isomorphic to a tape, but they're 
not tape. That's my point.

 > If you recorded all user input from any
> device and fed it to a TM,

... you would need to use something other than a TM to do that.

> it'd still work the same.

For *some* meaning of "work." Certainly if you tried to do that with (say) 
google's self-driving automobile, you'd be in trouble if the computer in the 
car didn't have a connection to the laser eye thing.

>> One TM can't program another TM at all, because a TM
>> can only write to its own tape.
>
> I'm not sure I'm following,

I don't know how else to say it. If you have two turing machines sitting 
next to each other in a room, the one can't program the other. By 
definition, the I/O of a turing machine is too limited to allow that. The 
output of one machine is not suitable as the program for the other machine.

It's really not all that deep. I just found it amusing when made 
self-referential.

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

Darren New <dne### [at] sanrrcom> wrote:
> On 4/9/2012 1:12, Warp wrote:
> > Darren New<dne### [at] sanrrcom>  wrote:
> >> A Turing machine can decompress a representation of an MP3 file into a
> >> representation of where the speaker would be at each given moment, but it
> >> can't actually play the music.
> >
> >    I don't understand what that has to do with solving a problem. It sounds
> > to me like you are using a fallacy of equivocation.

> If the problem is "I want to know what song this is" or "I want to listen to 
> some music", then you haven't really solved the problem.

  Why would pattern recognition or playing music be unsolvable in a TM?

  If you are talking about abstract problems (those which fall more under
the purview of philosophy) rather than problems that can be represented as
a program, you are committing a fallacy of equivocation (namely, you are
using two different meanings of the word "problem").

  My original question was: Are there *provably solvable* (in the mathematical
sense) problems that cannot be solved with a TM. (If you can prove them to
be solvable, then it kind of implies that you can present algorithms to
solve them.)

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

-- 
                                                          - Warp

Post a reply to this message

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

Darren New <dne### [at] sanrrcom> wrote:
> 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.

  If you go that path, then a TM cannot solve *anything at all* because
it can't read anything from anywhere nor write anything anywhere or do
anything else.

  (If you try to answer "it can solve something that's stored on the tape"
then you are contradicting yourself because you just claimed that "by
definition" there's no interface to write external data to the tape for
the TM to solve. Thus by your "by definition" a TM does nothing because
there's no way to interact with it.)

-- 
                                                          - Warp

Post a reply to this message

On 4/13/2012 1:45, Warp wrote:
> definition" there's no interface to write external data to the tape for
> the TM to solve.

There's no TM hardware to write to the tape. Presumably a human can also 
read and write the tape.

Of course, mathematically speaking, yes, there's no way to interact with a 
TM at all, but I think most people would consider eyeballing the tape and 
doing some conversion into some useful results to be acceptable. But 
eyeballs don't come with TMs, only with humans.

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