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