Re: [Algorithms] Turing machine question

[Danny K. <dr...@we...>]

> Assuming that "box" corresponds to a 1 and "no box" 
> corresponds to a 0 
> on the tape, then no, you definitely can't; you can't even 
> simulate an 
> unbounded binary counter with that model! No matter how many 
> boxes/bits 
> you give it initially, at some point it will run out of bits... 
> literally.

I'm not sure it's quite that simple. The machine can definitely count, by
making a space between two boxes. If it wants to count to 5, all it needs is
to make 1000001. To multiply that number by 2, it can use a third box as a
placeholder, then double each space. There's a lot of computation that can
be done in that way. The number itself could have godel-numbered
instructions which might be possible to unpack and run in some clever way. I
agree that it feels like the domain is far too finite to be able to do
everything, but I don't think proving it would be quite so cut-and-dried.

 Danny