Многоленточная машина Тьюринга



Скачать 11.39 Kb.
Дата30.12.2012
Размер11.39 Kb.
ТипДокументы
Многоленточная машина Тьюринга.



1 выходное – нельзя читать или корректировать.
головка неподвижная, ленты двигаются в разных направлениях
такт работы: считывание символов со всех лент, кроме выходной, шина состояния, запись новых символов, сдвиг лент

2. Применимость – машина применима к некоторому слову, если начав работать с ним, она формулирует какой-то результат на ленте и останавливается.
Самоприменима («С»), т.е. применима к своей собственной записи.

Обозначается: Р((Р))
Р : 0 => 1; 1 => 0




B: 1) ? {, 2}

  1. HLT


B – применима только к пустому слову, т.е. несамоприменима («Н»).

Проблема самоприменимости: отыскание такого алгоритма, который бы для любой программы определял её самоприменимость.




«Н» S((P))=<пустое слово>

«С» S((P))=< пустое слово >



«Н» R((P))=< пустое слово >

«C» R((P))= не определен
R = B0S
Применима ли R к своей собственной записи?
«Н» R((R))=< пустое слово > «С»

«С» R((R))= не определен «Н»

неопределен

исходная посылка неверна

Нет машины, которая определяла бы проблему самоприменимости.
Основываясь на неразрешимости этой проблемы, в теории алгоритмов доказывается, что неразрешима проблема применимости.

Похожие:

Многоленточная машина Тьюринга iconАлгоритм: определение и основные свойства. Классические машины Тьюринга. Тезис Тьюринга
Машина Тьюринга: принцип действия, описание работы. Построение алгоритмов для реализации на машинах Тьюринга
Многоленточная машина Тьюринга iconНормальные алгоритмы и тезис Маркова. Преобразование машин Тьюринга в нормальные алгоритмы. Понятие алгоритмической разрешимости. Задачи об остановке и печати машин Тьюринга
Машину Тьюринга, способную обрабатывать свою таблицу, мы назовем самоананализирующей машиной Тьюринга. Самоанализирующая машина-...
Многоленточная машина Тьюринга iconУрок №5-6 тема «Машина Тьюринга» Цель урока: изучение математического уточнения понятия алгоритма в виде воображаемой машины Тьюринга
Тьюринга; знать принцип работы мт; уметь читать и выполнять программы, написанные для мт; уметь строить программу для мт; знать тезис...
Многоленточная машина Тьюринга iconАлгоритмы. История. Типы алгоритмов. Машина
Тьюринга. Машина состояний и логическая структура алгоритма. Блок-схема алгоритма. Нормальный алгоритм. Программный монитор
Многоленточная машина Тьюринга iconЛабораторная работа №2 «Машина Поста»
Сконструируйте машину Тьюринга, которая выступит в качестве двоично-восьмеричного дешифратора
Многоленточная машина Тьюринга iconДискретная математика, часть Теория алгорифмов
Машина Тьюринга для копирования двоичного слова произвольной длины в прямом порядке
Многоленточная машина Тьюринга iconДисконтинуальное заполнение трехмерного пространства тетраэдрическими частицами. Молекулярная динамика как трехмерная машина Тьюринга вообще и вычисление в частности. Структура воды и макромолекул как частный случай

Многоленточная машина Тьюринга iconСложность вычислений
Многоленточные машины Тьюринга. Время и зона вычисления, связь между ними. Другие варианты машин Тьюринга
Многоленточная машина Тьюринга iconТьюринг, Алан Матисон А́лан Матисон Тью́ринг
Предложенная им в 1936 году абстрактная вычислительная «Машина Тьюринга», позволила формализовать понятие алгоритма и до сих пор...
Многоленточная машина Тьюринга iconПрограмма в полном объеме реализует правила русских шашек. Основная особенность: Самообучение программы в процессе игры
Выбор противника (машина-машина, машина-человек, человек-машина, человек-человек)
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org