Ис­пол­ни­тель МТ пред­став­ля­ет собой чи­та­ю­щую и за­пи­сы­ва­ю­щую го­лов­ку, ко­то­рая может пе­ре­дви­гать­ся вдоль бес­ко­неч­ной го­ри­зон­таль­ной ленты, раз­делённой на рав­ные ячей­ки. В каж­дой ячей­ке на­хо­дит­ся ровно один сим­вол из ал­фа­ви­та ис­пол­ни­те­ля (мно­же­ство сим­во­лов A  =  {a₀, a₁, ..., a_n − 1}), вклю­чая спе­ци­аль­ный пу­стой сим­вол a₀.

Время ра­бо­ты ис­пол­ни­те­ля де­лит­ся на дис­крет­ные такты (шаги). На каж­дом такте го­лов­ка МТ на­хо­дит­ся в одном из мно­же­ства до­пу­сти­мых со­сто­я­ний Q  =  {q₀, q₁, ..., q_n − 1}. В на­чаль­ный мо­мент вре­ме­ни го­лов­ка на­хо­дит­ся в на­чаль­ном со­сто­я­нии q₀.

На каж­дом такте го­лов­ка обо­зре­ва­ет одну ячей­ку ленты, на­зы­ва­е­мую те­ку­щей ячей­кой. За один такт го­лов­ка ис­пол­ни­те­ля может пе­ре­ме­стить­ся в ячей­ку спра­ва или слева от те­ку­щей, не меняя на­хо­дя­щий­ся в ней сим­вол, или за­ме­нить сим­вол в те­ку­щей ячей­ке без сдви­га в со­сед­нюю ячей­ку. После каж­до­го такта го­лов­ка пе­ре­хо­дит в новое со­сто­я­ние или остаётся в преж­нем со­сто­я­нии.

Про­грам­ма ра­бо­ты ис­пол­ни­те­ля МТ задаётся в таб­лич­ном виде.

В пер­вой стро­ке пе­ре­чис­ле­ны все воз­мож­ные сим­во­лы в те­ку­щей ячей­ке ленты, в пер­вом столб­це  — воз­мож­ные со­сто­я­ния го­лов­ки. На пе­ре­се­че­нии i⁠-й стро­ки и j⁠-го столб­ца на­хо­дит­ся ко­ман­да, ко­то­рую вы­пол­ня­ет МТ, когда го­лов­ка обо­зре­ва­ет j⁠-й сим­вол, на­хо­дясь в i⁠-м со­сто­я­нии. Если пара «сим­вол  — со­сто­я­ние» не­воз­мож­на, то клет­ка для ко­ман­ды остаётся пу­стой.

Каж­дая ко­ман­да со­сто­ит из трёх эле­мен­тов, раз­делённых за­пя­ты­ми: пер­вый эле­мент  — за­пи­сы­ва­е­мый в те­ку­щую ячей­ку сим­вол ал­фа­ви­та (может сов­па­дать с тем, ко­то­рый там уже за­пи­сан). Вто­рой эле­мент  — один из четырёх сим­во­лов «L», «R», «N», «S». Сим­во­лы «L» и «R» озна­ча­ют сдвиг в левую или пра­вую ячей­ки со­от­вет­ствен­но, «N»  — от­сут­ствие сдви­га, «S»  — за­вер­ше­ние ра­бо­ты ис­пол­ни­те­ля МТ после вы­пол­не­ния те­ку­щей ко­ман­ды.

Сдвиг про­ис­хо­дит после за­пи­си сим­во­ла в те­ку­щую ячей­ку. Тре­тий эле­мент  — новое со­сто­я­ние го­лов­ки после вы­пол­не­ния ко­ман­ды.

На­при­мер, ко­ман­да 0, L, q3 вы­пол­ня­ет­ся сле­ду­ю­щим об­ра­зом: в те­ку­щую ячей­ку за­пи­сы­ва­ет­ся сим­вол «0», затем го­лов­ка сдви­га­ет­ся в со­сед­нюю слева ячей­ку и пе­ре­хо­дит в со­сто­я­ние q3.

При­ведём при­мер вы­пол­не­ния про­грам­мы, за­дан­ной таб­лич­но. На ленте за­пи­са­но не­из­вест­ное не­ну­ле­вое ко­ли­че­ство рас­по­ло­жен­ных под­ряд в со­сед­них ячей­ках сим­во­лов «Z», все осталь­ные ячей­ки ленты за­пол­не­ны пу­стым сим­во­лом «λ». В на­чаль­ный мо­мент вре­ме­ни го­лов­ка на­хо­дит­ся на не­из­вест­ном не­ну­ле­вом рас­сто­я­нии спра­ва от са­мо­го пра­во­го сим­во­ла «Z».

Про­грам­ма.

за­ме­ня­ет на ленте все сим­во­лы «Z» на «X» и оста­нав­ли­ва­ет ис­пол­ни­те­ля в пер­вой ячей­ке слева от по­сле­до­ва­тель­но­сти сим­во­лов «X».

Воз­мож­ное на­чаль­ное со­сто­я­ние ис­пол­ни­те­ля.

...

λ

λ

Z

Z

Z

Z

λ

...

Ко­неч­но со­сто­я­ние ис­пол­ни­те­ля после за­вер­ше­ния вы­пол­не­ния про­грам­мы.

...

λ

X

X

X

X

λ

λ

...

Вы­пол­ни­те за­да­ние.

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

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

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