Применение машин тьюринга к словам

а) 111а₀1 а₀1;

б) 1111;

в) 1а₀1а₀1 а₀1?

Если машина останавливается, то какое слово получается в результате, какая ячейка и в каком состоянии обозревается?

КОМПОЗИЦИЯ, ИТТЕРАЦИЯ, РАЗВЕТВЛЕНИЕ

Пусть машины Т₁ и Т₂ имеют соответственно программы П ₁ и П _2. Предположим, что внутренние алфавиты этих машин не пересекаются и что - некоторое заключительное состояние машины Т₁, а - какое-либо начальное состояние машины Т₂. Заменим всюду в программе П ₁ состояние на состояние и полученная программа П определяет машину Т, называемую композицией машин Т1 и Т2 (по паре состояний (,)) и обозначаемую через Т₁◦Т₂ или Т₁Т₂ (более подробно: Т=Т(Т₁,Т₂, (,)). Внешний алфавит композиции Т₁Т₂ является объединением внешних алфавитов машин Т₁ и Т_2.

1)

a) P=1³0²1² б) Р=1⁴01

2)

а) Р=1¹0²1³01² , б) Р=1²0101³

3)

a) P=1²01³01², б) Р=1²01²0²1²

итерацией машины Т (по паре состояний (,)).

1. 
   i=1,
   

2. 
   i=1,
   

3. 
   i=3,
   

Пусть машины Т₁ , Т₂, Т₃ имеют соответственно программы П ₁, П₂, П_3. Предположим, что внутренние алфавиты этих машин не пересекаются. Пусть и - некоторые различные заключительные состояния машины Т₁. Заменим всюду в программе П₁ состояние некоторым начальным состоянием машины Т₂, а состояние - некоторым начальным состоянием машины Т₃. Затем новую программу объединим с программами П₂ и П_3. Полученная программа П определяет машину Т= Т(Т1(,),Т2(,),Т3), называемую разветвлением машин Т₂ и Т₃, управляемым машиной Т1 .

Найти результат применения разветвления машины Т= Т(Т1(,),Т2(,),Т3), к слову Р (q₂₀ – заключительное состояние машины T₂, а q₃₀ – заключительное состояние машины T₃).

1) a) P=101³, b) P=1³01

1) 2)

3)

4. 
   f(x)-? В начальной конфигурации обозревается крайняя правая единица ленты
   
5. 
   f(x,y)-? В начальной конфигурации обозревается крайняя правая единица ленты