How do I find largest subsequence in turing?

Question

In college I came across this and I couldn't find an answer for it yet.

We're given an 8-bit sequence as input on a single-tape Turing machine. For example:

01001101

The challenge is to count the largest adjacent subsequence of ones in such an input and write that count as a decimal digit at the left side of the input, separated by a hash symbol. For the example, the count is 2:

2#01001101 

I can correctly count and write the first subsequence, and so I have this on tape (for the example):

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

How can this be achieved?

Answer 1

The requirement to have the result stored as a decimal digit (0-8) can lead to a lot of states: states to add one to a digit and states to compare one such digit with another.

We can avoid comparing one digit to another (avoiding 9x9 = 81 transitions) by first storing the result in unary notation, i.e. by a repetition of a single symbol. That symbol could be 2 for instance. Then the very last step will be to convert that unary result to a decimal digit. This way we only need to implement the counting logic: one state for each digit and a transition to increment it, and one to write it.

The nice thing about the unary notation is that it is trivial to keep track of the maximum result. We could write the maximum so far with a series of 3 and overwrite it by the current count using 2.

To keep track of which 1 we have already processed, temporarily mark it, for instance with a blank. Restore it once we are ready to mark another one.

Example:

Input: 01110110

First initialise the left side and prefix two hashes. The leftmost hash will get replaced in the very last phase of the algorithm:

##01110110

Then find the first 1 and mark it:

##0_110110

...and also log it (we use 2 for the "current" group of 1):

2##0_110110

Then see if there is an adjacent 1. This is the case, so unmark and mark the next:

2##01_10110

...and prefix a 2 for it:

22##01_10110

Same thing to get the third 1 logged:

222##011_0110

The next time we look for an adjacent 1 we have no match, so we change the state to denote we start a new group of 1. Then mark that 1 as before:

222##01110_10

Before we log this at the left side, first make the current count we have more permanent by changing it to 3:

333##01110_10

...and now log the first 1 of the next group we had found with a 2:

332##01110_10

We can find an adjacent 1, and so this results in:

322##011101_0

One more scan follows where we reach the end of the input, and so we can go to the last phase where we count the number of digits we have at the left, and write the result instead of the hash:

3#01110110

Transition table

Here is a transition for the above described algorithm:

state	read	write	move head	next state
start	0 or 1		left	init##
init##	_	#	left	init#
init#	_	#	right	scan
scan	# or 0		right	scan
scan	1	_	left	lognew
scan	_		left	collect
lognew	0, 1, 2 or #		left	lognew
lognew	_ or 3		right	clear2
logmore	0, 1, 2 or #		left	logmore
logmore	_ or 3	2	right	more
clear2	2	3	right	clear2
clear2	#		left	put2
put2	_ or 3	2	right	more
more	0, 1, 2 or #		right	more
more	_	1	right	ismore
ismore	1	_	left	logmore
ismore	0		right	scan
ismore	_		left	collect
collect	0, 1, 2, 3 or #		left	collect
collect	_		right	sum0
sum0	2 or 3	_	right	sum1
sum0	#	0	right	halt
sum1	2 or 3	_	right	sum2
sum1	#	1	right	halt
sum2	2 or 3	_	right	sum3
sum2	#	2	right	halt
sum3	2 or 3	_	right	sum4
sum3	#	3	right	halt
sum4	2 or 3	_	right	sum5
sum4	#	4	right	halt
sum5	2	_	right	sum6
sum5	#	5	right	halt
sum6	2	_	right	sum7
sum6	#	6	right	halt
sum7	2	_	right	sum8
sum7	#	7	right	halt
sum8	#	8	right	halt

And a runnable snippet with the same transition table, where you can enter your own 8-digit input to test this implementation:

createTuring({
    transitions: [
        { state: "start",   read: "01",             move: "L", nextState: "init##"  },
        { state: "init##",  read: "_",  write: "#", move: "L", nextState: "init#"   },
        { state: "init#",   read: "_",  write: "#", move: "R", nextState: "scan"    },
        { state: "scan",    read: "#0",             move: "R", nextState: "scan"    },
        { state: "scan",    read: "1",  write: "_", move: "L", nextState: "lognew"  },
        { state: "scan",    read: "_",              move: "L", nextState: "collect" },
        { state: "lognew",  read: "012#",           move: "L", nextState: "lognew"  },
        { state: "lognew",  read: "_3",             move: "R", nextState: "clear2"  },
        { state: "logmore", read: "012#",           move: "L", nextState: "logmore" },
        { state: "logmore", read: "_3", write: "2", move: "R", nextState: "more"    },
        { state: "clear2",  read: "2",  write: "3", move: "R", nextState: "clear2"  },
        { state: "clear2",  read: "#",              move: "L", nextState: "put2"    },
        { state: "put2",    read: "_3", write: "2", move: "R", nextState: "more"    },
        { state: "more",    read: "012#",           move: "R", nextState: "more"    },
        { state: "more",    read: "_",  write: "1", move: "R", nextState: "ismore"  },
        { state: "ismore",  read: "1",  write: "_", move: "L", nextState: "logmore" },
        { state: "ismore",  read: "0",              move: "R", nextState: "scan"    },
        { state: "ismore",  read: "_",              move: "L", nextState: "collect" },
        { state: "collect", read: "0123#",          move: "L", nextState: "collect" },
        { state: "collect", read: "_",              move: "R", nextState: "sum0"    },
        { state: "sum0",    read: "23", write: "_", move: "R", nextState: "sum1"    },
        { state: "sum0",    read: "#",  write: "0", move: "R", nextState: "halt"    },
        { state: "sum1",    read: "23", write: "_", move: "R", nextState: "sum2"    },
        { state: "sum1",    read: "#",  write: "1", move: "R", nextState: "halt"    },
        { state: "sum2",    read: "23", write: "_", move: "R", nextState: "sum3"    },
        { state: "sum2",    read: "#",  write: "2", move: "R", nextState: "halt"    },
        { state: "sum3",    read: "23", write: "_", move: "R", nextState: "sum4"    },
        { state: "sum3",    read: "#",  write: "3", move: "R", nextState: "halt"    },
        { state: "sum4",    read: "23", write: "_", move: "R", nextState: "sum5"    },
        { state: "sum4",    read: "#",  write: "4", move: "R", nextState: "halt"    },
        { state: "sum5",    read: "2",  write: "_", move: "R", nextState: "sum6"    },
        { state: "sum5",    read: "#",  write: "5", move: "R", nextState: "halt"    },
        { state: "sum6",    read: "2",  write: "_", move: "R", nextState: "sum7"    },
        { state: "sum6",    read: "#",  write: "6", move: "R", nextState: "halt"    },
        { state: "sum7",    read: "2",  write: "_", move: "R", nextState: "sum8"    },
        { state: "sum7",    read: "#",  write: "7", move: "R", nextState: "halt"    },
        { state: "sum8",    read: "#",  write: "8", move: "R", nextState: "halt"    },
    ],
    initState: "start",
    tape: "01101110",
});

<script src="https://trincot.github.io/turing.js"></script>

Note that this is not the most efficient implementation. It is possible to do the job with just one sweep to the right and back to the left, but it would need quite a few more states and transitions.

Answer 2

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

Answer 3

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.