How do I find largest subsequence in turing?

Question

In college I came across this and I couldn't seem to find an answer for it yet (it's not a homework, just a riddle). Let's say you have input in Turing machine:

01001101 (8 bit sequence)

How do you count the largest subsequence of ones in such an input and get correct output 2#01001101? (2 because there are two ones near each other).

I can correctly count and write the first subsequence and so I have this on tape :

1#01001101

but then I have no idea how to count other subsequences of ones and not overwrite the result by a lower number (of the last subsequence). Do you have any ideas?

edit: Only one scratch tape to work on.

Answer 1

This is conceptually easy, but quite cumbersome to program (like anything non-trivial on a Turing machine). Here's an outline of an algorithm:

• Make sure there are two scratch tapes, one for storing the length of the run of zeros under the read head, one for storing the longest run seen (let's call the tapes N and Max, and store unary numbers on both). Both are initially empty.
• When you see a zero, write an extra 1 to N.
• When you see a one, rewind Max and N, then write the contents of N to Max, keeping the content beyond the end of N (so copying "111" over "1111" retains "1111", but copying "11111" over it produces "11111"). Then wipe N.
• When you're at the end, copy the content of Max (maybe converted to binary) to the beginning of the main tape.

This is really a translation of the straightforward algorithm:

N = Max = 0
for all x in the input:
    if x == 0:
        N += 1
    else:
        Max = max(N, Max)
        N = 0
output Max

where the variables are replaced by scratch tapes.

Answer 2

4294967289, thats the answer, dont believe me just try adding 1 to that number on turing, it'll say number too large