Задача 10. Проимитируйте работу машины с такой программой (табл

Проимитируйте работу машины с такой программой (табл. 13) для исходной записи на ленте:

Из примеров 9, 10, 11 видно, что для решения даже простых задач нужны довольно сложные машины Тьюринга. Естественно возникает вопрос: нельзя ли «собрать», сконструировать машины Тьюринга путем соединения нескольких более простых, элементарных машин?

В примере 9 мы могли бы поместить одну за другой машину С и три машины А.

В примерах 10, 11 мы могли бы сначала сконструировать машины для частных задач и затем «собрать» из них нужную машину. Из этих примеров видно также, что наряду с простым соединением машин (когда машина М' должна работать независимо от того, какая буква стояла в последней обозреваемой ячейке перед остановкой М) была бы желательна возможность и их дифференцированного соединения, т.е. такого, что если в последней обозреваемой ячейке перед остановкой машины М стояла буква s₀, то дальше должна работать машина М₁, иначе, т. е. если там стояла буква |, — то машина M₂.

Даны две машины Тьюринга М₁ и М₂, имеющие общий алфавит А = {s₀, s₁, s₂, …, s_k} и состояния q₀, q₁, q₂,..., q_p и q'₀, q'₁, q'₂,..., q'_m соответственно. Композицией машин M₁ и M₂ называется машина, обозначаемая М₁°М₂, имеющая алфавит А и состояния q₁, q₂,..., q_p, q'₁, q'₂,..., q'_m, q'₀ (начальное состояние машины M₁°M₂ - начальное состояние машины M₁, т.е. q₁, заключительное состояние - заключительное состояние машины М₂, т.е. q'₀).

Программа этой машины строится из программ машин М₁ и M₂ (см. табл. 14).

Таблица 14

В соответствии с этим определением машину из примера 9 мы могли бы записать так: ((С°А)°А)°А.