Gathering nonconsecutive 1's by a Turing machine

33 Views Asked by At

S. Barry Cooper comments his output convention for $\mathbb{N}\rightarrow\mathbb{N}$ Turing machines like this:

Outputting $n$ as $n$ possibly nonconsecutive $1$'s is very natural. [...] We can achieve [gathering them together consecutively] with a suitable "cleaning up" program.

If I understand correctly this suitable "cleaning up" program cannot be a Turing machine.

What then does Cooper mean in this context?

1

There are 1 best solutions below

4
On

You can fix the situation in the following way. Add two new symbols to mark the leftmost and rightmost ends of the work tape that you've ever been through. Given a Turing machine, it's easy to construct another one which maintains these symbols and otherwise behaves the same. Now it's easy to gather the 1's since you only have to look for them in this finite marked range.