Задача 10. Проимитируйте работу машины с такой программой (табл
Проимитируйте работу машины с такой программой (табл. 13) для исходной записи на ленте:
Из примеров 9, 10, 11 видно, что для решения даже простых задач нужны довольно сложные машины Тьюринга. Естественно возникает вопрос: нельзя ли «собрать», сконструировать машины Тьюринга путем соединения нескольких более простых, элементарных машин? В примере 9 мы могли бы поместить одну за другой машину С и три машины А. В примерах 10, 11 мы могли бы сначала сконструировать машины для частных задач и затем «собрать» из них нужную машину. Из этих примеров видно также, что наряду с простым соединением машин (когда машина М' должна работать независимо от того, какая буква стояла в последней обозреваемой ячейке перед остановкой М) была бы желательна возможность и их дифференцированного соединения, т.е. такого, что если в последней обозреваемой ячейке перед остановкой машины М стояла буква s0, то дальше должна работать машина М1, иначе, т. е. если там стояла буква |, — то машина M2.
Даны две машины Тьюринга М1 и М2, имеющие общий алфавит А = {s0, s1, s2, …, sk} и состояния q0, q1, q2,..., qp и q'0, q'1, q'2,..., q'm соответственно. Композицией машин M1 и M2 называется машина, обозначаемая М1°М2, имеющая алфавит А и состояния q1, q2,..., qp, q'1, q'2,..., q'm, q'0 (начальное состояние машины M1°M2 - начальное состояние машины M1, т.е. q1, заключительное состояние - заключительное состояние машины М2, т.е. q'0). Программа этой машины строится из программ машин М1 и M2 (см. табл. 14).
Таблица 14
В соответствии с этим определением машину из примера 9 мы могли бы записать так: ((С°А)°А)°А.
|
