algorithm - How do I find largest subsequence in turing? -

algorithm - How do I find largest subsequence in turing? -

in college came across , couldn't seem find reply yet (it's not homework, riddle). let's have input in turing machine:

01001101 (8 bit sequence)

how count largest subsequence of ones in such input , right output 2#01001101? (2 because there 2 ones near each other).

i can correctly count , write first subsequence , have on tape :

1#01001101

but have no thought how count other subsequences of ones , not overwrite result lower number (of lastly subsequence). have ideas?

edit: 1 scratch tape work on.

this conceptually easy, quite cumbersome programme (like non-trivial on turing machine). here's outline of algorithm:

make sure there 2 scratch tapes, 1 storing length of run of zeros under read head, 1 storing longest run seen (let's phone call tapes n , max, , store unary numbers on both). both empty. when see zero, write 1 n. when see one, rewind max , n, write contents of n max, keeping content beyond end of n (so copying "111" on "1111" retains "1111", copying "11111" on produces "11111"). wipe n. when you're @ end, re-create content of max (maybe converted binary) origin of main tape.

this translation of straightforward algorithm:

n = max = 0 x in input: if x == 0: n += 1 else: max = max(n, max) n = 0 output max

where variables replaced scratch tapes.

algorithm computer-science turing-machines