Turing Machines

[Mike]

Just a note on Turing Machines. I liked how crude/simplistic the
example was in the book. And it led me to think it must be the most
basic Turing Machine possible.

Simple Binary TM
- 2-way infinite tape
- 5 functions: read, move left, move right, write 0, write 1

The encoding of the TM impressed me, from a quadruple of integers for
each transition... to a pair of integers at each transition (listed in
order)... to a single integer (using prime decomposition). One must
note the information implicitly stored in the machine (like the order
of the states and transitions, start state, and halt state). I assume
every possible transition must be listed, otherwise how do you know if
a transition was skipped? With the thought of additional implicit
information, I was far less impressed, because you could take any
advanced computer program, and hash the binary into a single
hexadecimal number, which would basically be achieving the same thing,
correct?

Could there be a simpler TM, with less implied information? Can you
explicitly encode everything, or must there be some sort of meta-data?

Also, check out this Lego Turing Machine:
http://legoofdoom.blogspot.com/2009/01/turing-machine-demonstration-video.html

[David]

> With the thought of additional implicit
> information, I was far less impressed, because you could take any
> advanced computer program, and hash the binary into a single
> hexadecimal number, which would basically be achieving the same thing,
> correct?

This would only work with perfect hashing (for a one-to-one mapping),
but in general, yes. In fact you can do it with the source code as
well, since the set of all programs is enumerable, a program being a
finite sequence of characters taken from a finite alphabet (the ASCII
or Unicode encoding).

> Could there be a simpler TM, with less implied information?  Can you
> explicitly encode everything, or must there be some sort of meta-data?

i am not sure what you mean here.

> Also, check out this Lego Turing Machine:http://legoofdoom.blogspot.com/2009/01/turing-machine-demonstration-v...

This is a really cool Lego robot. Since we have a few of those in the
department, it would be great if we could rebuild it and use it in our
theory course.... Any volunteers?

[Mike]

Apparently google ate my first attempt at replying here. Let me try
again..

> > Could there be a simpler TM, with less implied information?  Can you
> > explicitly encode everything, or must there be some sort of meta-data?
>
> i am not sure what you mean here.
>

What I was getting at was a TM that didn't have to work under pre-
existing rules. For example, the book describes the smallest integer
of their TM encoding was 210. This is neat, but means nothing unless
you know how to decode and reconstruct the TM. Is there a way to have
a self-executing encoding of some sorts?

The more I think about it, the more the question seems trivial, and
most likely impossible. Every scenario I can imagine, the machine is
always running on top of some other set of preconceived notions.
Examples being a TM encoding, or machine code running directly on
hardware, either way there is some sort of interface or external
ruleset to guide these encodings and programs. I hope this makes more
sense, although I'm not sure we need to spend time here. This almost
sounds like a slippery slope to biology, DNA encoding, and life
itself, haha!