Машина внешний алфавит

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

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

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

Вычислимые функции и разрешимые предикаты. Каждая машина Тьюриига М вычисляет частичную функцию (рм нз Л в А, отображающую вход а в результат работы МТ иа входе а ири условии, что результат работы является словом во внешнем алфавите. Для входов, иа которых машина не останавливается илн результат содержит символы из <5 Л, функция 1рм ие определена. Пз определения ясно. [c.19]

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

Возможности машины Тьюрннга при таком неформальном обсуждении — это возможности человека с ограниченной памятью, карандашом и ластиком, которому вручили неограниченной (бесконечной) толщины тетрадь. Страницы тетради пмеют ограниченный размер (все возможные варнанты заполнения страницы образуют алфавит МТ нри строгом описании). Па первых страницах тетради записано входное слово — ио одному символу (из внешнего алфавита) на страницу. Человек может лнстать тетрадь, стирать символы, записывать новые. Заканчивается эта его деятельность тем, что он закрывает тетрадь (сдвиг головки влево в положении 0) и возвращает результат своей работы. [c.21]

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

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