Математическая логика и теория алгоритмов

это не сделано, то предполагается, что читающая головка находится на первой (самой левой) букве слова Р. Рассмотрим несколько примеров. 1. Пусть задана машина Т командами: q^lRq] qxSoiqQ, а на ленте записано слово Р=] (рис.б.З). Легко убедиться, что машина Т, начав работу с первой буквы слова Р, приписывает к нему слева по одной букве 1 на каждом шаге, никогда при этом не останавли­ ваясь. Следовательно, эта машина неприменима к слову Р. 2. Машина, заданная командами; qoSoRqo qoS]Rqo qoS2Rqo qoSkRqo где ни одно из Sj (1< i-^ к) не совпадает с символом 1, движется по ленте вправо, пока не встретит вхождение (если такое вообще име­ ется) символа 1, после чего останавливается, ^ 1^1 А Рис, 6.3 3. Машина Г, заданная командами qoaRqo qobRqa qoSoaqi, как легко убедиться, приписывает к любому слову Р алфавита {а,Ь} справа букву а и останавливается. 237