Примеры построения машины Тьюринга

Рассмотрим сначала несколько примеров с полным алфавитом. Пусть начальная конфигурация имеет вид , а машина Тьюринга управляется функциональной схемой, представленной в табл. 3.3.

Таблица 3.3

	a0	a1	a2
q1
q2
q3
q4

Так как управляющий головкой обозревается буква , а машина находится в состоянии , при этом пусть вырабатывается команда , т.е. головка сдвигается влево, заменяется на , состояние меняется на , т.е. получается конфигурация . Следующая конфигурация будет такой – , третья – , четвертая – , пятая – . Таким образом, приходим в начальное состояние. Процесс работы машины начал повторяться, и, следовательно, конечный результат не может быть получен, т.е. данная машина Тьюринга не применима к исходной информации.

Пусть теперь для той же машины начальная информация . Тогда, действуя аналогично, придем к следующим конфигурациям: , . Так как машина, перешла в начальное состояние, то слово – результат ее работы, и машина применим к исходной информации.

Видно, что понятие машины Тьюринга возникает в результате прямой попытки разложить интуитивно известные вычислительные процедуры на элементарные операции. Тьюринг привел ряд доводов в пользу того, что повторения его элементарных операций было бы достаточно для проведения любого возможного вычисления.

Если данное состояние описывается машинным словом М, то машинноеслово, описывающее следующее состояние машины, будет обозначаться через М ⁽¹⁾. Далее аналогично М ^{( i +1)}=(M ^{( i )})⁽¹⁾, i = 0,1,2,…. Переход машины Тьюринга из начального в последующие состояния изображается в виде цепочки слов M |- M ⁽¹⁾ |- M ⁽²⁾ |- … Чтобы описывать работу машины Тьюринга более удобным образом, текущие состояния машины пишут не внизу алфавита, а перед обозреваемой ячейкой. Например, пусть – символ остановки, а программа состоит из команд , и начальная конфигурация . Тогда

,

где 0 – символ пустой ячейки ленты машины. Если же начальная конфигурация , то

.

Таким образом, каждая машина Тьюринга с произвольными алфавитами А и Q и заданной программой переработки s -ку слов , записанных в алфавите А, в слово , если машина применима к начальной информации, и машина не применима к s -ке слов , если выражение (слово) после ее работы имеет неопределенное значение. Словарная функция называется вычислимой по Тьюрингу, если она вычислима на подходящей машине Тьюринга.

Теорема 11. Все словарные функции, вычислимые по Тьюрингу, являются частично рекурсивными.

Тезис Тьюринга: Любая вычислимая функция вычислима по Тьюрингу.

Теорема 12. Для каждой частично рекурсивной словарной функции , определенной на совокупности слов какого-нибудь алфавита , существует машина Тьюринга с символами и подходящими внутренними состояниями, которая правильно вычисляет функцию F.

Рассмотрим несколько машин Тьюринга, преобразующих машинные слова одного заданного вида в машинные слова другого заданного вида. Программы машины будем писать в столбец.

Поиск по сайту: