Машина пустой символ

Можно строить машины Тьюринга, вычисляющие рекурсивные функции. Для примера опишем машину, вычисляющую функцию Цх) = X + 1 — одну из базовых рекурсивных функций. Внешний алфавит будет состоять из двух символов О (пустой символ) и 1. Целое неотрицательное число х будет представляться в виде соответствующего числа следующих друг за другом символов 1. [c.27]

Пусть Т(п) — максимальное время, которое может пройти до остановки машины Тьюринга с п состояниями и п символами алфавита, если её запустить на пустой ленте. Докажите, что функция Т п) растёт быстрее любой вычислимой всюду определённой функции Ь п), то есть Vn-n[T(n)/h(n)] = +ОС. [c.27]

Лента разделена на клетки одинаковой величины в каждой из них может быть помещен ровно один символ из некоторого конечного алфавита, содержащего также и пустой символ (внешний алфавит). Головка в каждый данный момент времени (на каждом шаге) может прочитать один символ из клетки, расположенной под ней, записать в эту клетку новый символ и передвинуться на одну клетку вправо или влево (или остаться на месте). Логический блок может находиться в одном из конечного числа внутренних состояний 5= 5 2.(внутренний алфавит). Работает логический блок следующим образом заставляет головку прочитать символ, стоящий на ленте под нею. В зависимости от прочитанного символа и своего внутреннего состояния он заставляет головку записать на ленте в клетку под головкой некоторый символ заставляет головку передвинуться на одну клетку вправо, влево или остаться на месте изменяет свое собственное состояние. Если в результате предыдущих действий символ, расположенный под головкой, положение головки и состояние логического блока не изменяются, машина останавливается. В противном случае логический блок возвращается к началу работы. [c.26]

Если машина применима к исходному данному, она приводит к результату пустому слову, если под головкой находится буква Ао, или к слову, ограниченному с двух сторон пустыми символами, если одна из букв этого слова (непустая) находится под головкой. Таким образом, машина Тьюринга реализует некоторую функцию, устанавливая соответствие между исходными данными (к которым она применима) и результатами. [c.27]

Первая строка означает, что машина поставила метку в первой позиции н понесла вправо символ, который в ней стоял. Вторая строка означает, что на пустом слове машина сразу останавливается. [c.142]

Часть клеток матрицы информационной таблицы обычно бывает пустой. Это может происходить по двум причинам. Во-первых, объект и класс характеристик, указанный на входе таблицы могут быть несовместимы. Это означает, что данному объекту несвойственна характеристика, сформулированная в наименовании класса. Во-вторых, могут отсутствовать сведения по ряду характеристик. Поэтому при записи информационных таблиц в памяти машины- целесообразно применять специальные меры по экономии места. Одной из таких мер может быть введение логической шкалы перед каждой строкой или перед каждым столбцом матрицы (в зависимости от того, в каком порядке проводилась ее линейная развертка). Логическая шкала содержит столько двоичных знаков, сколько клеток в матрице информационной таблицы. Символом О в шкале обозначаются клетки информационной таблицы, которые соответствуют несовместимым парам кодов объектов и характеристик. Остальные клетки матрицы обозначаются символом 1. После логической шкалы записывается массив отсылочных адресов к значениям характеристик, который содержит столько позиций, сколько единиц имеется в логической шкале. Если сведения по какому-либо значению характеристики отсутствуют, то вместо отсылочного адреса проставляется нулевой код. В дальнейшем при пополнении сведений об объектах этот код может быть заменен на отсылочный адрес к значению характеристики. Буквенные коды значений характеристик, входящих в состав строки или столбца информационной таблицы, записываются Е порядке их поступления. В начале каждого буквенного кода указывается количество ячеек памяти, занимаемое значением характеристики. [c.220]

Пусть А — некоторый алфавит, ап — натуральное число. Пусть М — машина Тьюрпнга с внешним алфавитом А и . Построим частичную функцию срм,п нз (Л )" в А так 1рм,п(о 1, , сеп] = У, если результат работы машины М па входе а фа2ф. . . а совпадает со словом у. Если машина не останавливается илн на ленте записано что-ппбудь ие то (наиример, символы пе пз алфавита А п т.п.), то рм,п сч, . . ., Оп) не определена. [c.20]

Ограничимся указанием. Для любой вычислимой функщ-ш Ь п) ири достаточно больших п среди машин с п символами алфавита н п состояниями, останавливающихся иа пустом входе, можно найти и такую, которая вычисляет пЬ(п), а затем вычитает из этого числа по единице, пока не дойдёт до нуля. [c.145]

Справочник химика 21

Химия и химическая технология