def execute_MT(MT,input):
    T=MT["program"]
    tape=["*"]+input
    state=MT["start"]
    position=1
    history=[{"state":state, "position":position, "tape": []+tape}]
    step=0
    while 1:
       step=step+1
       if position>=len(tape):
           tape.append("*")
       symbol_under_head=tape[position]
       action=T[(state,(symbol_under_head))]
       state=action[0]
       symbol_to_write=action[1][0]
       tape[position]=symbol_to_write
       move=action[1][1]
       if move=="L": position=position-1
       if move=="R": position=position+1
       history.append({"state":state, "position":position, "tape": []+tape})
       if state==MT["stop"] or step>1000:
           break
    return history

MT={
 'k': 1,
 'start': 's1',
 'stop': 'q',
 'program': {
 #(Состояние, символы на лентах) -> (новое состояние, (действия по каждой ленте))
  ('s1', ('1')): ('s2', (('*','R'))),
  ('s2', ('1')): ('s2', (('1','R'))),
  ('s2', ('*')): ('s3', (('*','R'))),
  ('s3', ('*')): ('s4', (('1','L'))),
  ('s3', ('1')): ('s3', (('1','R'))),
  ('s4', ('1')): ('s4', (('1','L'))),
  ('s4', ('*')): ('s5', (('*','L'))),
  ('s5', ('1')): ('s5', (('1','L'))),
  ('s5', ('*')): ('s1', (('1','R'))),
  ('s1', ('*')): ('q',  (('*','')))
 }
}