Статья Автор: Лебедев Дмитрий Алексеевич

Реализуем МТ как процедуру и решаем задачи

Реализуем МТ как процедуру, которая получает на вход:

начальную последовательность df
словарь состояний DS, где ключ состояние, а значение словарь позиций (ключ позиция, значение - описание действий)
начальное состояние (ts) и начальную позицию (pos)

Возвращает:

изменяет df
финальное состояние и финальную позицию
код возврата (причину завершения работы)

Подпрограмма:

не изменяет длину списка df
умеет обрабатывать команды перемещения указателя:
- R - сдвиг вправо на одну позицию
- L - сдвиг влево на одну позицию
- N - позиция указателя не изменяется
- S - остановка (штатное завершения программы)
обрабатывает остановку и возвращает код:
- 0 - остановка штатная
- 1 - не найдено состояние в словаре состояний
- 2 - не найдена позиция для состояния в словаре действий
- 3 - попытка получить значение вне позиций списка

Работу программы приведем на примере получения следующего значения в двоичной системе.
Будем выполнять программу, пока длина списка будет меньше 7
Начальное значение ' 0 '

def MT(df,DS,tps) :
  ts, pos = tps # распаковка начальных значений состояния и позиции головки
  if pos == - 1 : pos = len(df) - 1 # упрощение передачи начало СПРАВА
  Err = 0 # код завершения
  while True :
    if (ts in DS) == False :
      Err = 1 # состояние не найдено
      break
    if pos < 0 or pos >= len(df) :
      Err = 3 # выход за пределы последовательности
      break
    a = df[pos]
    if (a in DS[ts]) == False:
      Err = 2
      break
    xa, yp, zt = DS[ts][a] # распаковка действий
    if xa != a : df[pos] = xa # изменение значения
    ts = zt # изменение состояния 
    if yp == 'R' : pos +=1 # движение вправо
    elif yp == 'L' : pos -=1 # движение влево
    elif yp == 'S' : break # остановка программы
  return Err,ts, pos
# Инициализация начальных значений

df = [' ', '0',' ']
DS = {0:{' ':(' ','L',1)}}
DS[1] = {' ':('1','S',2),'0':('1','S',2), '1':('0','L',1)}
while len(df) < 7 :
  ans = MT(df,DS,(0,-1))
  print(*df,sep ='')
  if df[0] != ' ' : df = [' '] + df

Теперь можно использовать процедуру MT и описывать нужные словари.
Попробуем решить задачу "Сортировка", то есть получение последовательности, в которой
вначале все нули, а затем все 1
Например из #101101# надо получить #001111#
Попробуем создать таблицу:

Состояние ноль - движение ВПРАВО до 1( переход в состояние один) или #(остановка)
Состояние один - движение ВПРАВО до 0(переход в состояние два без движения головки) или #(остановка)
Состояние два - запись 1, ВЛЕВО, состояние три
Состояние три - запись 0, ВЛЕВО, состояние четыре
Состояние четыре - ВЛЕВО до # (переход в состояние ноль)

Возможны и другие решения

# Инициализация начальных значений
st= f'#{int(input()):b}#'
print(st)
df = [x for x in st]
DS = {0:{'#':('#','R',0),'0':('0','R',0),'1':('1','R',1)}}
DS[1] = {'#':('#','S',1),'0':('0','N',2),'1':('1','R',1)}
DS[2] = {'0':('1','L',3)}
DS[3] = {'1':('0','L',4)}
DS[4] = {'#':('#','N',0),'0':('0','L',4),'1':('1','L',4)}

ans = MT(df,DS,(0,0))
print(*df,sep ='')

Реализация с очередью (то есть универсальная)

from collections import deque
def MT(tape,DS,tps) :
  ts, pos, blnk = tps # распаковка начальных значений состояния и позиции головки
  if pos == - 1 : pos = len(tape) -1 # упрощение передачи начало СПРАВА
  Err = 0 # код завершения
  while True :
    if (ts in DS) == False :
      Err = 1 # состояние не найдено
      break
    a = tape[pos]
    if (a in DS[ts]) == False:
      Err = 2
      break
    xa, yp, zt = DS[ts][a] # распаковка действий
    if xa != a : tape[pos] = xa # изменение значения
    ts = zt # изменение состояния 
    if yp == 'R' : 
      pos +=1 # движение вправо
      if pos == len(tape) : tape.append(blnk)
    elif yp == 'L' :
      if pos == 0 : tape.appendleft(blnk)
      else : pos -=1 # движение влево
    elif yp == 'S' : break # остановка программы
  return Err,ts, pos
# Инициализация начальных значений
blnk = ''
df = deque([blnk,'0' ,blnk])
print(df)
DS = {0:{blnk:(blnk,'L',1)}}
DS[1] = {blnk:('1','L',2),'0':('1','S',1), '1':('2','S',1), '2':('0','L',1)}
DS[2] = {blnk:(blnk,'S',2)}
for i in range (1580):
  ans = MT(df,DS,(0,-1,blnk))
  #print(ans)
print(*df,sep ='')

Печать