Re: [Algorithms] Turing machine question

[Olivier G. <gal...@po...>]

On Thu, Jul 16, 2009 at 10:10:42AM -0700, Jon Watte wrote:
> I thought that at first, too, but consider: Even if you represent 
> numbers with spaces, you will run out of bits for the number of numbers 
> that you'll need to represent. At most, you can represent (N-1) numbers 
> with N available bits (and that doesn't take into account the 
> book-keeping needed for applying any actual algorithm).

Countable infinity is still countable infinity.  You can encode a set
of positive integers as
  N = 2**i1 * 3**i2 * 5**i3 * 7**i4 * 11**i5 * ...
which is only one number.  Alternatively you can encode the tape for a
turing machine as a number too.  If you call Ti the value of the bit
at position i relative to the head, you can encode the tape state as
  N = sum(Ti * 2**(i > 0 ? 2*i : i<0 ? -2*i-1 : 0))

If the tape wall all 0 at start, the number of non-zero Ti is finite
so there's no convergence issue.

In practice, you can encode any finite or countably infinite digital
system state in one number (that's where names like Godel start to
fuse).  So, on a turing-ish tape, that means two bits are enough.
Converting the program to run on the 1-bit limited version is the hard
part though.  I have no idea whether it's actually possible.

  OG.