ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.03.2019
Просмотров: 1111
Скачиваний: 10
1) записывает некоторый символ S в видимую клетку (в частности, может быть записан тот же символ, что и был в ней, тогда содержимое этой клетки не меняется);
2) сдвигается на одну клетку влево (L), либо на одну клетку вправо (R), либо остается неподвижным ( ).
3) переходит в некоторое состояние q (в частности, может остаться в прежнем состоянии).
Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:
● Внешний алфавит. Конечное множество (например, А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ.
● Внутренний алфавит. Конечное множество состояний головки (автомата). Одно из состояний (например, q1) должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние останова.
● Таблица переходов. Описание поведения автомата (головки) в зависимости от состояния и считанного символа.
Виды МТ:
-
Многодорожечная машина Тьюринга
-
Машина Тьюринга с полубесконечной лентой
-
Многоленточная машина Тьюринга
Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:
● Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).
● Передвигаться на одну ячейку влево или вправо.
● Менять свое внутреннее состояние.
Если требуется написать достаточно сложную программу, для упрощения процесса программирования применяют операции композиции машин Тьюринга, т.е. построение сложной машины из более простых, при этом используют две операции: умножение машин Тьюринга и итерация машин Тьюринга.
-
Функция, вычислимая по Тьюрингу. Функция правильно вычислимая по Тьюрингу. Запись на ленте МТ значений аргументов функций. Запись результата вычислений на ленте. Зацикливание машины. Эквивалентность и суперпозиция машин Тьюринга. Тезис Тьюринга.
Ф-я наз-ся вычислимой по Тьюрингу, если существует машина Тьюринга, вычисляющая ее, т.е. такая машина Тьюринга, которая вычисляет ее значения для тех наборов значений аргументов, для которых функция определена, и работающая вечно, если функция для данного набора значений аргументов не определена.
Функция f называется правильно вычислимой по Тьюрингу, если существует машина Тьюринга Т, которая ее правильно вычисляет.
Теорема о зацикливании : Проблема зацикливания машины Тьюринга не является частично разрешимой.
МТ зацикливается, никогда не попадая на такт останова (например, автомат на каждом шаге сдвигается вправо и потому не может остановиться, т.к. лента бесконечна). В этом случае говорят, что МТ неприменима к заданному входному слову. Ни о каком результате при таком исходе не может идти и речи.
Лента, на которой записывается результат вычислений, движется со скоростью программной ленты и поэтому запись результата не вызывает замедления работы машины. Результат, записанный на ленту в двоичной системе, переводится в десятичную и отпечатывается на бумаге.
Эквивалентность МТ и частично-рекурсивных функций означает, что всякая частично-рекурсивная функция оказывается вычислимой по Тьюрингу и наоборот.
Если функции f(x1,x2,…,xn), g1 (x1,x2,…,xm), …, gn (x1,x2,…,xm) правильно вычислимы по Тьюрингу, то правильно вычислима и сложная функция (суперпозиция функций):
φ(x1,x2,…,xn)=f( g1 (x1,x2,…,xm),…, gn (x1,x2,…,xm)).
Тезис: любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга.
-
Нумерация алгоритмов. Нумерация машин Тьюринга. Существование невычислимых по Тьюрингу функций.
Множество
всех алгоритмов счетно. Ведь любой
алгоритм можно задать конечным описанием,
а множество всех конечных слов в
фиксированном алфавите счетно. Счетность
множества алгоритмов означает наличие
взаимно-однозначного соответствия
между алгоритмами и числами натурального
ряда, т.е. функции типа 
,
взаимно-однозначно отображающей слова
в алфавите
,
выбранном для описания алгоритмов в
числа натурального ряда. Такая
функция
называется
нумерацией алгоритмов,
а ее аргумент
-
номером алгоритма
при
нумерации
.
Для формального анализа различных проблем, связанных с машинами Тьюринга, удобно каждой машине присвоить числовой номер – целое положительное число. Способ Геделя основан на том, что, как известно из арифметики, любое целое положительное число A можно единственным способом представить в виде произведения простых множителей в виде:
Здесь 
-i-й
простой множитель числа А; ni –
степень, с которой данный множитель
входит в разложение числа А
Теперь посмотрим, как получить геделевский номер машины Тьюринга. Такая машина задана своими правилами. Каждое правило можно представить как строку символов
Мы уже знаем, как читать такую строку: если машина находится в состоянии Qi и читает символ Sj, то она переходит в состояние Qk , записывает символ Sz вместо Sj и выполняет действие A={оставить ленту на месте; сдвинуть ленту влево на одну ячейку; сдвинуть ленту вправо на одну ячейку}.
Проблема остановки имеет следующую формулировку: найти алгоритм, позволяющий по номеру машины Тьюринга и произвольной конфигурации определить, придет ли данная машина в заключительное состояние, начав работать в этой конфигурации.
Проблема самоприменимости является частным случаем проблемы остановки и заключается в том, чтобы определить, применима ли машина к своему номеру.
-
Примеры алгоритмически неразрешимых проблем.
Проблема остановки имеет следующую формулировку: найти алгоритм, позволяющий по номеру машины Тьюринга и произвольной конфигурации определить, придет ли данная машина в заключительное состояние, начав работать в этой конфигурации.
Проблема самоприменимости является частным случаем проблемы остановки и заключается в том, чтобы определить, применима ли машина к своему номеру. Проблема эквивалентности алгоритмов; По двум произвольным заданным алгоритмам (например, по двум машинам Тьюринга) определить, будут ли они выдавать одинаковые выходные результаты на любых исходных данных.
-
Меры сложности алгоритмов. Временная и емкостная сложность. Переборные и распознавательные задачи.
сложность алгоритма – количество необходимых для решения задачи ресурсов как функция от ее размера.
Рассмотрим некоторые из них:
1. Временная сложность алгоритма – «время» выполнения алгоритма, измеряемое в «шагах» (инструкциях алгоритма, которые необходимо выполнить для достижения результата)
2. Емкостная сложность алгоритма – необходимый для работы алгоритма объём памяти машины.
3. Схемная сложность алгоритма – минимальный размер схемы из функциональных элементов, вычисляющей заданную (булеву) функцию .
4. Коммуникационная сложность алгоритма – минимальное число бит, которыми нужно обменяться участникам вычисления некоторой функции .
В дальнейшем будем подробно рассматривать вычисление временной сложности алгоритмов. Этот критерий является важным, но не единственным при оценке эффективности алгоритмов. Например, в силу следующих соображений
1. Эффективный по времени алгоритм может быть неэффективным по объему памяти.
2. Эффективные по времени, но сложные алгоритмы нежелательны, если готовые программы будут поддерживать лица, не участвовавшие в их написании.
3. В численных алгоритмах точность и устойчивость не менее важны, чем их временная эффективность.
4. Если программа будет использована только несколько раз, стоимость её написания превосходит стоимость времени ее выполнения. Финансово более выгоден алгоритм простой в реализации.
Переборная задача характеризуется экспоненциальным множеством вариантов, среди которых нужно найти решение, и может быть решена алгоритмом полного перебора. Переборный алгоритм имеет экспоненциальную сложность и может хорошо работать только для небольших размеров задачи. С ростом размера задачи число вариантов быстро растет, и задача становится практически неразрешимой методом перебора.
распознавательные задачи – задачи, имеющие распознавательную форму. В распознавательной форме суть задачи сводится к распознаванию некоторого свойства, а ее решение – один из двух ответов: «да» или «нет». С точки зрения математической логики задаче распознавания свойства соответствует предикат Р(х), где х – множество фактических значений входных переменных задачи.