Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Структура программы машины Тьюринга с заданным внешним алфавитом и алфавитом внутренних состояний.





Что собой представляет машина Тьюринга?

Машина Тьюринга состоит из бесконечной в обе стороны ленты, разделенной на ячейки, и автомата (головки), которая управляется программой.
Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.

Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие: Внешний алфавит. Конечное множество (например, А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ. Внутренний алфавит. Конечное множество состояний головки (автомата). Одно из состояний (например, q1) должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние останова. Таблица переходов. Описание поведения автомата (головки) в зависимости от состояния и считанного символа.

Вычислимые по Тьюрингу функции

Будем рассматривать функции f от одной или нескольких переменных, заданных на множестве N = {0, 1, 2, …, n, …} натуральных чисел или его подмножествах (частичные функции) и принимающие значения на множестве N. Определение 5.8. Функция f(x1, x2, …, xn) называется вычислимой, если существует алгоритм, позволяющий вычислять ее значения для тех переменных, для которых она определена, и работающий бесконечно, если функция для данного набора переменных не определена.



Определение 5.9. Функция f(x1, x2, …, xn) называется вычислимой по Тьюрингу, если существует машина Тьюринга, вычисляющая эту функцию.

Тезис Тьюринга (Основная гипотеза теории алгоритмов).

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

Правильная вычислимость функций на машине Тьюринга.

Определение 1. Будем говорить, что машина Тьюринга пра­вильно вычисляет функцию f(x1, x2, ..., хп),, если начальное слово она переводит в слово и при этом в процессе работы не пристраивает к начальному слову но­вых ячеек на ленте ни слева, ни справа. Если же функция f не определена на данном наборе значений аргументов, то, начав работать из указанного положения, она никогда в процессе рабо­ты не будет надстраивать ленту слева.

Пример 1. Приведем программы машин Тьюринга, пра­вильно вычисляющих функции S(x) = х+ 1 и 0(х) = 0. Функция S(x) =х+ 1 осуществляет перевод: q101x0 => q001x+1. Ее программа:q10→ q2 П; q21→ q21 П; q20→ q31; q31→ q31 Л; q30→ q00. Функция O(x) = 0 осуществляет перевод: q101x0 => q000x+1. Ее программа: q10→ q2 0П; q21→ q21 П; q20→ q30Л; q31→ q40; q40→ q30Л, q30→ q00. Соответствующую машину Тьюринга обозна­чили О.

Композиция машин Тьюринга.

С математической точки зрения машина Тьюринга — просто определенный алгоритм для переработки слов. Операции композиции, выполняемые над алгоритмами, позволяют образовы-вать новые, более сложные алгоритмы из ранее известных простых алгоритмов. Поскольку машина Тьюринга—алгоритм, то операции композиции применимы и к машинам Тьюринга. Рассмотрим основные из них, а именно: произведение, возве-дение в степень, итерацию. Пусть заданы машины Тьюринга Т1 и Т2, имеющие какой-то общий внешний алфавит А = {а0, а1,..., аm} и внутренние алфавиты Q1 = {q0, q1,..., qn} и cоответственно Q2 = {q0,q1,…,qt}. Композитом, или произведением, машины Т1 на машину T2 будем называть машину Т с тем же внешним алфавитом А= {а0, а1,..., аm}, внутренним алфавитом Q = {q0, q1,...,qn, qn+1, ...,qn+t} и программой, получающейся следующим образом. Во всех командах Т1 содержащих заключитель-ный символ q0, заменяем его на символ qn+1. Все остальные символы в командах T1 оставляем неизменными. В командах Т2, напротив, символ q0 оставляем неизменным, но зато каждый из остальных символов заменяем символом qn+j. Совокупность всех команд Т1 и Т2, измененных указанным способом, и будет программой композита или произведения машин T1 и T2.Произведение машины T1 на машину Т2 обозначается через Т = T1 • T2, или Т = T1 * Т2. Таким образом, машина Т есть произведение машин Т1 и T2, если последовательная работа этих двух машин эквивалентна работе одной машины Т.

Рекурсивные функции.

Рекурси́вная фу́нкция (от лат. recursio — возвращение) — это числовая функция числового аргумента, которая в своей записи содержит себя же. Такая запись позволяет вычислять значения на основе значений , подобно рассуждению по индукции. Чтобы вычисление завершалось для любого , необходимо, чтобы для некоторых функция была определена нерекурсивно (например, для ).

 









Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2018 zdamsam.ru Размещенные материалы защищены законодательством РФ.