Как найти наибольшую подпоследовательность в turing?

Question

В колледже я наткнулся на это, и я пока не мог найти ответа для него (это не домашнее задание, а просто загадка). Допустим, у вас есть вход в машине Тьюринга:

01001101 (8 битой последовательность)

Как посчитать большую подпоследовательность из них в таком входе и получить правильный выход-# 01001101? (2, потому что они находятся рядом друг с другом).

я могу правильно считать и писать первую подпоследовательность и поэтому у меня есть это на ленте:

1 # 01001101

, но тогда я понятия не имею, как считать других подпоследовательности из них и не перезаписать результат меньшим числом (последней подпоследовательности). У тебя есть идеи?

Редактировать: Только одна скребковая лента для работы.

Answer 1

Это концептуально простой, но довольно громоздкий для программирования (как и все, что нетривиально на машине Тьюринга). Вот набросок алгоритма:

• Убедитесь, что два нуль ленты, один для хранения длины пробега нулей под считывающей головкой, один для хранения длинного пробега видел (назовую ленту N и Max и сохранить унарные номера на обоих). Оба изначально пусты.
• Когда вы видите нуль, напишите дополнительный номер от 1 до N.
• Когда вы видите один, перемотайте Макс и N, затем напишите содержимое от N до Max, сохранив содержимое за пределами конца N (так что копирование «111» над «1111» сохраняет «1111», но копирование «11111» над ним производит «11111»). Затем протрите N.
• Когда вы закончите, скопируйте содержимое Max (возможно, преобразованное в двоичное) в начало основной ленты.

Это действительно перевод простой алгоритм:

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

где переменные заменяются скретч ленты.

Answer 2

4294967289, тот ответ, не верите мне просто попробуйте добавить 1 к этому номеру на Тьюринга, это будет говорить число слишком велико