 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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] san rrcom> 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
|
|
| |
| |
|
|
|
|
| |
