Исполнитель МТ: машина Тьюринга

Исполнитель МТ — головка, которая движется вдоль бесконечной ленты из ячеек; в каждой ячейке записан ровно один символ алфавита, в том числе пустой символ λ. За один такт головка в состоянии q, обозревая символ в текущей ячейке, выполняет команду из таблицы: записывает символ, затем сдвигается влево (L), вправо (R), остаётся на месте (N) или останавливается (S), и переходит в новое состояние. Команда «1, L, q1» означает: записать 1, сдвинуться влево, перейти в состояние q1. В начальный момент головка находится в состоянии q0.

На ленте в соседних ячейках записана последовательность из 1000 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

После выполнения программы на ленте осталось ровно 312 нулей. Определите максимально возможное число нулей в исходной последовательности.

L = 'λ'
prog = {
    ('q0', 'λ'): ('λ', 'L', 'q1'),
    ('q1', 'λ'): ('λ', 'S', 'q1'),
    ('q1', '1'): ('0', 'S', 'q1'),
    ('q1', '0'): ('1', 'L', 'q1'),
}

def run(seq):
    tape = dict(enumerate(seq))
    pos, st = len(seq), 'q0'          # головка справа от последовательности
    while True:
        w, mv, st2 = prog[(st, tape.get(pos, L))]
        tape[pos] = w
        st = st2
        if mv == 'S':
            return ''.join(c for k, c in sorted(tape.items()) if c != L)
        pos += -1 if mv == 'L' else 1

# крайний случай из рассуждения
seq = '0' * 311 + '1' * 1 + '0' * 688
after = run(seq)
print(after.count('0'))       # должно быть 312
print(seq.count('0'))

Исполнитель МТ — головка, которая движется вдоль бесконечной ленты из ячеек; в каждой ячейке записан ровно один символ алфавита, в том числе пустой символ λ. За один такт головка в состоянии q, обозревая символ в текущей ячейке, выполняет команду из таблицы: записывает символ, затем сдвигается влево (L), вправо (R), остаётся на месте (N) или останавливается (S), и переходит в новое состояние. Команда «1, L, q1» означает: записать 1, сдвинуться влево, перейти в состояние q1. В начальный момент головка находится в состоянии q0.

На ленте в соседних ячейках записана последовательность из 1500 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

После выполнения программы на ленте осталось ровно 1112 нулей. Определите максимально возможное число нулей в исходной последовательности.

L = 'λ'
prog = {
    ('q0', 'λ'): ('λ', 'L', 'q1'),
    ('q1', 'λ'): ('λ', 'S', 'q1'),
    ('q1', '0'): ('1', 'L', 'q2'),
    ('q1', '1'): ('0', 'L', 'q2'),
    ('q2', 'λ'): ('λ', 'S', 'q2'),
    ('q2', '0'): ('0', 'L', 'q1'),
    ('q2', '1'): ('1', 'L', 'q1'),
}

def run(seq):
    tape = dict(enumerate(seq))
    pos, st = len(seq), 'q0'          # головка справа от последовательности
    while True:
        w, mv, st2 = prog[(st, tape.get(pos, L))]
        tape[pos] = w
        st = st2
        if mv == 'S':
            return ''.join(c for k, c in sorted(tape.items()) if c != L)
        pos += -1 if mv == 'L' else 1

# крайний случай из рассуждения
seq = '01' * 362 + '0' * 776
after = run(seq)
print(after.count('0'))       # должно быть 1112
print(seq.count('0'))

Исполнитель МТ — головка, которая движется вдоль бесконечной ленты из ячеек; в каждой ячейке записан ровно один символ алфавита, в том числе пустой символ λ. За один такт головка в состоянии q, обозревая символ в текущей ячейке, выполняет команду из таблицы: записывает символ, затем сдвигается влево (L), вправо (R), остаётся на месте (N) или останавливается (S), и переходит в новое состояние. Команда «1, L, q1» означает: записать 1, сдвинуться влево, перейти в состояние q1. В начальный момент головка находится в состоянии q0.

На ленте в соседних ячейках записана последовательность из 1200 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

После выполнения программы на ленте осталось ровно 431 единица. Определите максимально возможное число единиц в исходной последовательности.

L = 'λ'
prog = {
    ('q0', 'λ'): ('λ', 'L', 'q1'),
    ('q1', 'λ'): ('λ', 'S', 'q1'),
    ('q1', '0'): ('0', 'L', 'q1'),
    ('q1', '1'): ('1', 'L', 'q2'),
    ('q2', 'λ'): ('λ', 'S', 'q2'),
    ('q2', '0'): ('0', 'L', 'q1'),
    ('q2', '1'): ('0', 'L', 'q1'),
}

def run(seq):
    tape = dict(enumerate(seq))
    pos, st = len(seq), 'q0'          # головка справа от последовательности
    while True:
        w, mv, st2 = prog[(st, tape.get(pos, L))]
        tape[pos] = w
        st = st2
        if mv == 'S':
            return ''.join(c for k, c in sorted(tape.items()) if c != L)
        pos += -1 if mv == 'L' else 1

# крайний случай из рассуждения
seq = '0' * 338 + '1' * 862
after = run(seq)
print(after.count('1'))       # должно быть 431
print(seq.count('1'))

Исполнитель МТ — головка, которая движется вдоль бесконечной ленты из ячеек; в каждой ячейке записан ровно один символ алфавита, в том числе пустой символ λ. За один такт головка в состоянии q, обозревая символ в текущей ячейке, выполняет команду из таблицы: записывает символ, затем сдвигается влево (L), вправо (R), остаётся на месте (N) или останавливается (S), и переходит в новое состояние. Команда «1, L, q1» означает: записать 1, сдвинуться влево, перейти в состояние q1. В начальный момент головка находится в состоянии q0.

На ленте в соседних ячейках записана последовательность из 1200 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

После выполнения программы на ленте осталось ровно 515 нулей. Определите максимально возможное число нулей в исходной последовательности.

L = 'λ'
prog = {
    ('q0', 'λ'): ('λ', 'L', 'q1'),
    ('q1', 'λ'): ('λ', 'S', 'q1'),
    ('q1', '0'): ('0', 'L', 'q1'),
    ('q1', '1'): ('1', 'L', 'q2'),
    ('q2', 'λ'): ('λ', 'S', 'q2'),
    ('q2', '1'): ('1', 'L', 'q2'),
    ('q2', '0'): ('1', 'L', 'q1'),
}

def run(seq):
    tape = dict(enumerate(seq))
    pos, st = len(seq), 'q0'          # головка справа от последовательности
    while True:
        w, mv, st2 = prog[(st, tape.get(pos, L))]
        tape[pos] = w
        st = st2
        if mv == 'S':
            return ''.join(c for k, c in sorted(tape.items()) if c != L)
        pos += -1 if mv == 'L' else 1

# крайний случай из рассуждения
seq = '0' * 516 + '10' * 341 + '1' * 2
after = run(seq)
print(after.count('0'))       # должно быть 515
print(seq.count('0'))

Исполнитель МТ — головка, которая движется вдоль бесконечной ленты из ячеек; в каждой ячейке записан ровно один символ алфавита, в том числе пустой символ λ. За один такт головка в состоянии q, обозревая символ в текущей ячейке, выполняет команду из таблицы: записывает символ, затем сдвигается влево (L), вправо (R), остаётся на месте (N) или останавливается (S), и переходит в новое состояние. Команда «1, L, q1» означает: записать 1, сдвинуться влево, перейти в состояние q1. В начальный момент головка находится в состоянии q0.

На ленте в соседних ячейках записана последовательность из 1500 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

После выполнения программы на ленте осталось ровно 931 нуль. Определите минимально возможное число нулей в исходной последовательности.

L = 'λ'
prog = {
    ('q0', 'λ'): ('λ', 'L', 'q1'),
    ('q1', 'λ'): ('λ', 'S', 'q1'),
    ('q1', '0'): ('1', 'L', 'q2'),
    ('q1', '1'): ('0', 'L', 'q2'),
    ('q2', 'λ'): ('λ', 'S', 'q2'),
    ('q2', '0'): ('0', 'L', 'q1'),
    ('q2', '1'): ('1', 'L', 'q1'),
}

def run(seq):
    tape = dict(enumerate(seq))
    pos, st = len(seq), 'q0'          # головка справа от последовательности
    while True:
        w, mv, st2 = prog[(st, tape.get(pos, L))]
        tape[pos] = w
        st = st2
        if mv == 'S':
            return ''.join(c for k, c in sorted(tape.items()) if c != L)
        pos += -1 if mv == 'L' else 1

# крайний случай из рассуждения
seq = '1' * 1138 + '01' * 181
after = run(seq)
print(after.count('0'))       # должно быть 931
print(seq.count('0'))

Исполнитель МТ — головка, которая движется вдоль бесконечной ленты из ячеек; в каждой ячейке записан ровно один символ алфавита, в том числе пустой символ λ. За один такт головка в состоянии q, обозревая символ в текущей ячейке, выполняет команду из таблицы: записывает символ, затем сдвигается влево (L), вправо (R), остаётся на месте (N) или останавливается (S), и переходит в новое состояние. Команда «1, L, q1» означает: записать 1, сдвинуться влево, перейти в состояние q1. В начальный момент головка находится в состоянии q0.

На ленте в соседних ячейках записана последовательность из 1200 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

После выполнения программы на ленте осталось ровно 592 нуля. Определите максимально возможное число нулей в исходной последовательности.

L = 'λ'
prog = {
    ('q0', 'λ'): ('λ', 'L', 'q1'),
    ('q1', 'λ'): ('1', 'S', 'q1'),
    ('q1', '1'): ('0', 'L', 'q1'),
    ('q1', '0'): ('1', 'S', 'q1'),
}

def run(seq):
    tape = dict(enumerate(seq))
    pos, st = len(seq), 'q0'          # головка справа от последовательности
    while True:
        w, mv, st2 = prog[(st, tape.get(pos, L))]
        tape[pos] = w
        st = st2
        if mv == 'S':
            return ''.join(c for k, c in sorted(tape.items()) if c != L)
        pos += -1 if mv == 'L' else 1

# крайний случай из рассуждения
seq = '0' * 592 + '1' * 607 + '0' * 1
after = run(seq)
print(after.count('0'))       # должно быть 592
print(seq.count('0'))

Исполнитель МТ — головка, которая движется вдоль бесконечной ленты из ячеек; в каждой ячейке записан ровно один символ алфавита, в том числе пустой символ λ. За один такт головка в состоянии q, обозревая символ в текущей ячейке, выполняет команду из таблицы: записывает символ, затем сдвигается влево (L), вправо (R), остаётся на месте (N) или останавливается (S), и переходит в новое состояние. Команда «1, L, q1» означает: записать 1, сдвинуться влево, перейти в состояние q1. В начальный момент головка находится в состоянии q0.

На ленте в соседних ячейках записана последовательность из 1000 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

После выполнения программы на ленте осталось ровно 292 единицы. Определите минимально возможное число единиц в исходной последовательности.

L = 'λ'
prog = {
    ('q0', 'λ'): ('λ', 'L', 'q1'),
    ('q1', 'λ'): ('λ', 'S', 'q1'),
    ('q1', '0'): ('0', 'L', 'q1'),
    ('q1', '1'): ('1', 'L', 'q2'),
    ('q2', 'λ'): ('λ', 'S', 'q2'),
    ('q2', '0'): ('0', 'L', 'q1'),
    ('q2', '1'): ('0', 'L', 'q1'),
}

def run(seq):
    tape = dict(enumerate(seq))
    pos, st = len(seq), 'q0'          # головка справа от последовательности
    while True:
        w, mv, st2 = prog[(st, tape.get(pos, L))]
        tape[pos] = w
        st = st2
        if mv == 'S':
            return ''.join(c for k, c in sorted(tape.items()) if c != L)
        pos += -1 if mv == 'L' else 1

# крайний случай из рассуждения
seq = '0' * 417 + '10' * 291 + '1' * 1
after = run(seq)
print(after.count('1'))       # должно быть 292
print(seq.count('1'))

Исполнитель МТ — головка, которая движется вдоль бесконечной ленты из ячеек; в каждой ячейке записан ровно один символ алфавита, в том числе пустой символ λ. За один такт головка в состоянии q, обозревая символ в текущей ячейке, выполняет команду из таблицы: записывает символ, затем сдвигается влево (L), вправо (R), остаётся на месте (N) или останавливается (S), и переходит в новое состояние. Команда «1, L, q1» означает: записать 1, сдвинуться влево, перейти в состояние q1. В начальный момент головка находится в состоянии q0.

На ленте в соседних ячейках записана последовательность из 800 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

После выполнения программы на ленте осталось ровно 280 нулей. Определите максимально возможное число нулей в исходной последовательности.

L = 'λ'
prog = {
    ('q0', 'λ'): ('λ', 'L', 'q1'),
    ('q1', 'λ'): ('λ', 'S', 'q1'),
    ('q1', '0'): ('0', 'L', 'q1'),
    ('q1', '1'): ('1', 'L', 'q2'),
    ('q2', 'λ'): ('λ', 'S', 'q2'),
    ('q2', '1'): ('1', 'L', 'q2'),
    ('q2', '0'): ('1', 'L', 'q1'),
}

def run(seq):
    tape = dict(enumerate(seq))
    pos, st = len(seq), 'q0'          # головка справа от последовательности
    while True:
        w, mv, st2 = prog[(st, tape.get(pos, L))]
        tape[pos] = w
        st = st2
        if mv == 'S':
            return ''.join(c for k, c in sorted(tape.items()) if c != L)
        pos += -1 if mv == 'L' else 1

# крайний случай из рассуждения
seq = '0' * 281 + '10' * 259 + '1' * 1
after = run(seq)
print(after.count('0'))       # должно быть 280
print(seq.count('0'))

Исполнитель МТ — головка, которая движется вдоль бесконечной ленты из ячеек; в каждой ячейке записан ровно один символ алфавита, в том числе пустой символ λ. За один такт головка в состоянии q, обозревая символ в текущей ячейке, выполняет команду из таблицы: записывает символ, затем сдвигается влево (L), вправо (R), остаётся на месте (N) или останавливается (S), и переходит в новое состояние. Команда «1, L, q1» означает: записать 1, сдвинуться влево, перейти в состояние q1. В начальный момент головка находится в состоянии q0.

На ленте в соседних ячейках записана последовательность из 1500 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

После выполнения программы на ленте осталось ровно 1024 нуля. Определите максимально возможное число нулей в исходной последовательности.

L = 'λ'
prog = {
    ('q0', 'λ'): ('λ', 'L', 'q1'),
    ('q1', 'λ'): ('λ', 'S', 'q1'),
    ('q1', '0'): ('1', 'L', 'q2'),
    ('q1', '1'): ('0', 'L', 'q2'),
    ('q2', 'λ'): ('λ', 'S', 'q2'),
    ('q2', '0'): ('0', 'L', 'q1'),
    ('q2', '1'): ('1', 'L', 'q1'),
}

def run(seq):
    tape = dict(enumerate(seq))
    pos, st = len(seq), 'q0'          # головка справа от последовательности
    while True:
        w, mv, st2 = prog[(st, tape.get(pos, L))]
        tape[pos] = w
        st = st2
        if mv == 'S':
            return ''.join(c for k, c in sorted(tape.items()) if c != L)
        pos += -1 if mv == 'L' else 1

# крайний случай из рассуждения
seq = '01' * 274 + '0' * 952
after = run(seq)
print(after.count('0'))       # должно быть 1024
print(seq.count('0'))

Исполнитель МТ — головка, которая движется вдоль бесконечной ленты из ячеек; в каждой ячейке записан ровно один символ алфавита, в том числе пустой символ λ. За один такт головка в состоянии q, обозревая символ в текущей ячейке, выполняет команду из таблицы: записывает символ, затем сдвигается влево (L), вправо (R), остаётся на месте (N) или останавливается (S), и переходит в новое состояние. Команда «1, L, q1» означает: записать 1, сдвинуться влево, перейти в состояние q1. В начальный момент головка находится в состоянии q0.

На ленте в соседних ячейках записана последовательность из 1200 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

После выполнения программы на ленте осталось ровно 200 нулей. Определите максимально возможное число нулей в исходной последовательности.

L = 'λ'
prog = {
    ('q0', 'λ'): ('λ', 'L', 'q1'),
    ('q1', 'λ'): ('λ', 'S', 'q1'),
    ('q1', '1'): ('0', 'S', 'q1'),
    ('q1', '0'): ('1', 'L', 'q1'),
}

def run(seq):
    tape = dict(enumerate(seq))
    pos, st = len(seq), 'q0'          # головка справа от последовательности
    while True:
        w, mv, st2 = prog[(st, tape.get(pos, L))]
        tape[pos] = w
        st = st2
        if mv == 'S':
            return ''.join(c for k, c in sorted(tape.items()) if c != L)
        pos += -1 if mv == 'L' else 1

# крайний случай из рассуждения
seq = '0' * 199 + '1' * 1 + '0' * 1000
after = run(seq)
print(after.count('0'))       # должно быть 200
print(seq.count('0'))

Исполнитель МТ — головка, которая движется вдоль бесконечной ленты из ячеек; в каждой ячейке записан ровно один символ алфавита, в том числе пустой символ λ. За один такт головка в состоянии q, обозревая символ в текущей ячейке, выполняет команду из таблицы: записывает символ, затем сдвигается влево (L), вправо (R), остаётся на месте (N) или останавливается (S), и переходит в новое состояние. Команда «1, L, q1» означает: записать 1, сдвинуться влево, перейти в состояние q1. В начальный момент головка находится в состоянии q0.

На ленте в соседних ячейках записана последовательность из 1000 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

После выполнения программы на ленте осталось ровно 679 нулей. Определите минимально возможное число нулей в исходной последовательности.

Исполнитель МТ — головка, которая движется вдоль бесконечной ленты из ячеек; в каждой ячейке записан ровно один символ алфавита, в том числе пустой символ λ. За один такт головка в состоянии q, обозревая символ в текущей ячейке, выполняет команду из таблицы: записывает символ, затем сдвигается влево (L), вправо (R), остаётся на месте (N) или останавливается (S), и переходит в новое состояние. Команда «1, L, q1» означает: записать 1, сдвинуться влево, перейти в состояние q1. В начальный момент головка находится в состоянии q0.

На ленте в соседних ячейках записана последовательность из 1500 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

После выполнения программы на ленте осталось ровно 541 нуль. Определите максимально возможное число нулей в исходной последовательности.

Исполнитель МТ — головка, которая движется вдоль бесконечной ленты из ячеек; в каждой ячейке записан ровно один символ алфавита, в том числе пустой символ λ. За один такт головка в состоянии q, обозревая символ в текущей ячейке, выполняет команду из таблицы: записывает символ, затем сдвигается влево (L), вправо (R), остаётся на месте (N) или останавливается (S), и переходит в новое состояние. Команда «1, L, q1» означает: записать 1, сдвинуться влево, перейти в состояние q1. В начальный момент головка находится в состоянии q0.

На ленте в соседних ячейках записана последовательность из 800 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

После выполнения программы на ленте осталось ровно 380 единиц. Определите максимально возможное число единиц в исходной последовательности.

Исполнитель МТ — головка, которая движется вдоль бесконечной ленты из ячеек; в каждой ячейке записан ровно один символ алфавита, в том числе пустой символ λ. За один такт головка в состоянии q, обозревая символ в текущей ячейке, выполняет команду из таблицы: записывает символ, затем сдвигается влево (L), вправо (R), остаётся на месте (N) или останавливается (S), и переходит в новое состояние. Команда «1, L, q1» означает: записать 1, сдвинуться влево, перейти в состояние q1. В начальный момент головка находится в состоянии q0.

На ленте в соседних ячейках записана последовательность из 1500 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

После выполнения программы на ленте осталось ровно 537 нулей. Определите максимально возможное число нулей в исходной последовательности.

Исполнитель МТ — головка, которая движется вдоль бесконечной ленты из ячеек; в каждой ячейке записан ровно один символ алфавита, в том числе пустой символ λ. За один такт головка в состоянии q, обозревая символ в текущей ячейке, выполняет команду из таблицы: записывает символ, затем сдвигается влево (L), вправо (R), остаётся на месте (N) или останавливается (S), и переходит в новое состояние. Команда «1, L, q1» означает: записать 1, сдвинуться влево, перейти в состояние q1. В начальный момент головка находится в состоянии q0.

На ленте в соседних ячейках записана последовательность из 999 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

После выполнения программы на ленте осталось ровно 580 нулей. Определите максимально возможное число нулей в исходной последовательности.