Студопедия Главная Случайная страница Обратная связь

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

править]Машина Тьюринга, работающая на полубесконечной ленте





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

Рассмотрим доказательство, приведённое Ю. Г. Карповым в книге «Теория автоматов». Доказательство этой теоремы конструктивное, то есть мы дадим алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Во-первых произвольно занумеруем ячейки рабочей ленты МТ, то есть определим новое расположение информации на ленте:

Затем перенумеруем ячейки, причём будем считать, что символ «*» не содержится в словаре МТ:

Наконец, изменим машину Тьюринга, удвоив число её состояний, и изменим сдвиг головки считывания-записи так, чтобы в одной группе состояний работа машины была бы эквивалентна её работе в заштрихованной зоне, а в другой группе состояний машина работала бы так, как исходная машина работает в незаштрихованной зоне. Если при работе МТ встретится символ ‘*’, значит головка считывания-записи достигла границы зоны:

Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации. Очевидно, что слева от ограничивающих маркеров «*» лента в эквивалентной машине Тьюринга не используется.







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




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


Расчетные и графические задания Равновесный объем - это объем, определяемый равенством спроса и предложения...


Кардиналистский и ординалистский подходы Кардиналистский (количественный подход) к анализу полезности основан на представлении о возможности измерения различных благ в условных единицах полезности...


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

Разработка товарной и ценовой стратегии фирмы на российском рынке хлебопродуктов В начале 1994 г. английская фирма МОНО совместно с бельгийской ПЮРАТОС приняла решение о начале совместного проекта на российском рынке. Эти фирмы ведут деятельность в сопредельных сферах производства хлебопродуктов. МОНО – крупнейший в Великобритании...

ОПРЕДЕЛЕНИЕ ЦЕНТРА ТЯЖЕСТИ ПЛОСКОЙ ФИГУРЫ Сила, с которой тело притягивается к Земле, называется силой тяжести...

СПИД: морально-этические проблемы Среди тысяч заболеваний совершенно особое, даже исключительное, место занимает ВИЧ-инфекция...

Основные структурные физиотерапевтические подразделения Физиотерапевтическое подразделение является одним из структурных подразделений лечебно-профилактического учреждения, которое предназначено для оказания физиотерапевтической помощи...

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

Тема 2: Анатомо-топографическое строение полостей зубов верхней и нижней челюстей. Полость зуба — это сложная система разветвлений, имеющая разнообразную конфигурацию...

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