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