Cтраница 3
Пусть машина Тьюринга задана функциональной схемой. [31]
Сама машина Тьюринга кодируется цепочкой, получающейся конкатенацией в любом порядке кодов пятерок, представляющих ее функцию переходов. [32]
Существует машина Тьюринга с неразрешимой проблемой остановки. [33]
Эти машины Тьюринга будут нам полезны при рассмотрении вопроса о разрешимости. [34]
Имея машины Тьюринга, вычисляющие какие-то функции - g и h, построить машину, вычисляющую функцию, возникающую из g и Л примитивной рекурсией. [35]
Одна машина Тьюринга может иметь несколько различных описаний, поскольку четверки, ее задающие, можно записывать в строчку-описание в произвольном порядке. [36]
Пусть машина Тьюринга 7 правильно вычисляет функцию К ( х, у), а машина Т2 ( х) перерабатывает слово g OFO в lOl OFO. [37]
Неформально машина Тьюринга - очень примитивная программируемая вычислительная машина. Ее память состоит из бесконечной последовательности элементарных ячеек. Удобно полагать, что каждая ячейка помечена соответствующим целым числом. Она содержит символ из фиксированного конечного алфавита, содержащего п ( не менее двух) элементов. Специальный элемент называется пробел. Имеется головка, которая в каждый момент времени указывает одну из ячеек ленты памяти. Третьей составляющей машины является программа. [38]
Пусть машина Тьюринга Т начинает работать в некоторый ( начальный) момент времени. Слово, записанное в этот момент на ленте, называется исходным или начальным. [39]
Поскольку машины Тьюринга подробно описаны в литературе [2, 16], мы ограничимся кратким изложением проблемы. Особый элемент из S - b - обозначает пустую клетку. [40]
Пусть машины Тьюринга TI, Т и Тз задаются программами Щ, П2 и Пз соответственно. Считаем, что внутренние алфавиты этих машин попарно не пересекаются. [41]
Программа машины Тьюринга - это двумерная решетка, в каждой клетке которой хранятся три числа - коды символа, направления движения и состояния автомата. [42]
Работа машины Тьюринга складывается из следующих один за другим тактов. Очередное значениеy ( t l) записывается головкой в ячейку. [43]
Рассмотрим машины Тьюринга, вычисляющие элементарные арифметические функции, из которых строятся рекурсивные функции. [44]
Работа машины Тьюринга зависит от характера исходной записи ленты. [45]