Re: [Algorithms] Turing machine question

[Fabian G. <f.g...@49...>]

> 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.

To settle this, you'd need to define exactly what you mean by universality.

I'd state that a universal turing machine U is a TM that will, given a 
coded representation of another TM (let's call it M) and its input, 
produce the exact same output on the tape as running the original M with 
the given input directly if M halts on that input, if and only if M 
halts. And if M with the given input doesn't halt, then neither will U.

I'll further add the requirement that there be a fixed encoding for the 
TM input string; i.e. encoding a "0" or "1" input bit will always take 
the same amount of bits no matter where they are in the input string.

Expanding my example a bit: Assume a turing machine X that gets a binary 
number n as input, with the head initially just at right of the final 
digit. X will proceed to write exactly n ones starting at the initial 
head position, clear the rest of the tape to zero, and stop with the 
head at its initial position. This is a more precisely specified version 
of my binary counter example.

X is well-defined and will eventually halt on all inputs. Actually 
implementing X will involve some trickery such as padding the binary 
number somehow so that the start of the sequence of 1s can always be 
found, so it's not trivial, but it's not really complex either.

Now, X can be made to produce a string of 1s arbitrarily long given 
appropriate input. Doing a "left-shift" of n will only add a constant 
number of 1 bits (boxes), but double the number of "1" bits in the 
output. So you'll eventually run out of ones (boxes) for large enough n.

--

That's why I specifically mentioned a *binary* counter. If you allow 
arbitrary problem-specific transformations (like changing a binary into 
a unary counter), you can obviously work around the limitations for a 
lot longer, but you're not really executing the same algorithm.

I added the definition of universality (with the requirement of 
producing the same output, which is key here) to illustrate the point.

Kind regards,
-Fabian "ryg" Giesen