Студопедия — Задача 1. Какую работу выполнит машина Тьюринга, если она работает по программе:
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Задача 1. Какую работу выполнит машина Тьюринга, если она работает по программе:






Какую работу выполнит машина Тьюринга, если она работает по программе:

 

  s0 |
q1 |Нq0 |Пq1

Пусть перед началом работы машины ее память (лента) имеет вид

Согласно программе, обозревая ячейку, в которой хранится знак |, и находясь в состоянии q1 машина производит следующее действие: не производя никаких изменений в воспринимаемой ячейке, управляющая головка движется вправо и машина остается в состоянии q1

Состояние ленты после первого такта работы машины будет таким:

Дальнейшее действие приводит к остановке машины с состоянием ленты:

Таким образом, рассматриваемая машина отыскивает первую пустую ячейку справа от воспринимаемой, печатает на ней букву алфавита и останавливается, воспринимая эту ячейку.

Условимся представлять числа 0, 1, 2, 3,... словами в алфавите {|}: |, ||,

,

Соответственно. Для представления на ленте набора целых неотрицательных чисел x1, x2,..., xn мы будем писать соответствующее число раз букву |, оставляя в точности одну пустую ячейку между каждыми двумя словами (конечными последовательностями букв |). Так, набор чисел 3, 0, 2 запишется на ленте следующим образом:   s0 | | | | s0 | s0 | | | s0 s0   Учитывая это, работу рассмотренной машины (назовем ее машиной A) можно охарактеризовать следующим образом: машина A, воспринимая последнее число набора чисел (в стандартном положении), увеличивает его на единицу и останавливается, воспринимая полученное число. В дальнейшем мы будем иметь дело только с целыми неотрицательными числами (расширенным нулем множеством натуральных чисел) или наборами этих чисел и их записями в однобуквенном алфавите {|}.







Дата добавления: 2015-09-07; просмотров: 385. Нарушение авторских прав; Мы поможем в написании вашей работы!



Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

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

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Ситуация 26. ПРОВЕРЕНО МИНЗДРАВОМ   Станислав Свердлов закончил российско-американский факультет менеджмента Томского государственного университета...

Различия в философии античности, средневековья и Возрождения ♦Венцом античной философии было: Единое Благо, Мировой Ум, Мировая Душа, Космос...

Характерные черты немецкой классической философии 1. Особое понимание роли философии в истории человечества, в развитии мировой культуры. Классические немецкие философы полагали, что философия призвана быть критической совестью культуры, «душой» культуры. 2. Исследовались не только человеческая...

СИНТАКСИЧЕСКАЯ РАБОТА В СИСТЕМЕ РАЗВИТИЯ РЕЧИ УЧАЩИХСЯ В языке различаются уровни — уровень слова (лексический), уровень словосочетания и предложения (синтаксический) и уровень Словосочетание в этом смысле может рассматриваться как переходное звено от лексического уровня к синтаксическому...

Плейотропное действие генов. Примеры. Плейотропное действие генов - это зависимость нескольких признаков от одного гена, то есть множественное действие одного гена...

Методика обучения письму и письменной речи на иностранном языке в средней школе. Различают письмо и письменную речь. Письмо – объект овладения графической и орфографической системами иностранного языка для фиксации языкового и речевого материала...

Studopedia.info - Студопедия - 2014-2024 год . (0.012 сек.) русская версия | украинская версия