Алгоритм и машина Тьюринга




 

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

Для расширения понятия автомата как инструмента реализации алгоритмов нам понадобится ряд понятий.

Определение Конечное число элементов назовем словарем; элементы словаря называются символами (словами); последователь ности символов называются цепочками (предложениями); множест во выделенных предложений называется языком над словарем .

Обозначение - язык над словарем ; - множество всех цепочек.

Определение Грамматикой называется конечный механизм задания языка.

Приведем два таких механизма.

Определение Порождающей грамматикой языка называет ся конечный набор правил, позволяющий строить правильные предло жения и только их.

Определение Распознающей грамматикой языка называется

критерий принадлежности данной цепочки языку.

Роль распознающей грамматики может выполнять следующий автомат без выходов.

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

Определение Язык, для которого существует распознающий его автомат-распознаватель, называется автоматным языком.

_____

Определение Алгоритм – определенное на некотором языке конечное предписание (рецепт), задающее дискретную последователь ность исполняемых элементарных операций для решения задачи.

ЗАМЕЧАНИЕ Существует несколько формальных моделей

алгоритма: Геделя, Черча, Тьюринга, Маркова. Доказано, что

алгоритм, реализуемый в одной из этих моделей, реализуем и в

остальных.

Конечный автомат-распознаватель выполняет преобразование информации по определенным правилам, то есть реализует некоторый алгоритм обработки информации. Один из главных вопросов информа тики – построение автоматического устройства, реализующего алгори тмы. Мы показали, что не существует автомата-распознавателя, реализующего алгоритм задания языка , , как и не существует автомата, реализующего алгоритм умножения двух произвольных чисел. Для того чтобы обобщение понятия авто матно реализуемых алгоритмов было более наглядным, рассмотрим

такую «механическую» интерпретацию конечного автомата-распознавателя.

ЗАМЕЧАНИЕ Конечный автомат (КА) – это устройство с

конечным числом внутренних состояний, одним входом и одним

выходом. Вход реализован в виде считывающей головки, которая

движется вдоль входной ленты и потактово считывает содержимое

ее ячеек (буквы ). Выход реализуется виде печатающей голов

ки, которая синхронно движется вдоль выходной ленты и печатает

на ней выходной символ . При этом внутреннее состояние

автомата меняется с на . Функционирование КА, то есть его

программа, вполне определяется заданием вход-выходного отобра

жения с .

Определение Машиной Тьюринга (МТ) называется устройство с 1) одной бесконечной лентой, с которой считываются входные и куда впечатываются выходные символы, 2) одной головкой чтения-записи, которая может двигаться по рабочей ленте в любую сторону. На каждом такте МТ считывает символ из обозреваемой ячейки и:

1) изменяет свое состояние (на ) в зависимости от этого символа и

текущего состояния ,

2) впечатывает символ в обозреваемую ячейку и

3) головка чтения записи перемещается в направлении : влево (),

вправо () или остается на месте ().

Функционирование МТ, то есть программа машины Тьюринга – это конечный список пятерок , порождающих частичное отображение , где - входной и одновременно выходной алфавит, . Если в этой программе нет пары , то машина останавливается. На ленте присутствует знак "Останов" , который отделяет цепочки значащих символов.

При таком определении машина Тьюринга "перерабатывает" (заменяет) входную цепочку на выходную. То есть она является автоматом-преобразователем отдельных цепочек.

ЗАМЕЧАНИЕ Машина Тьюринга реализует алгоритм перемножения произвольных чисел. В качестве распознавателя МТ распознает, например, язык . Программой такой МТ является множество пятерок

.

Здесь - финальное состояние. Ее граф имеет вид

 

 

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

Пример Ю. Матиясевич доказал, что 10-ая проблема Гильберта алгоритмически неразрешима.

Элементы комбинаторики

 

Определение Произвольное подмножество из множества называется выборкой объема .

Определение Выборка называется упорядоченной (неупорядочен ной), если порядок следования элементов в ней существенен (не суще ственен).

Определение Упорядоченная выборки объема из элементов называется - размещением.

ЗАМЕЧАНИЕ Количество всевозможных -размещений

вычисляется по формуле .

Определение Упорядоченная выборка объема из набора

элементов называется перестановкой.

ЗАМЕЧАНИЕ Число всевозможных перестановок в группе из элементов вычисляется по формуле .

Определение Неупорядоченная выборка объема называется

- сочетанием.

ЗАМЕЧАНИЕ 1 Число сочетаний из во множестве из

элементов вычисляется по формуле .

ЗАМЕЧАНИЕ 2 Число всевозможных разбиений множества из

элементов на подмножеств объемов соответственно

вычисляется по формуле .

◄ Число всевозможных неупорядоченных выборок объема вычисляется по формуле . На втором шаге из оставшихся элементов можно произвести неупорядоченных выборок объема . И так далее. На последнем шаге из оставшихся элементов можно организовать неупорядоченных выборок объема . Искомое число всевозможных разбиений тогда равно

. ►

СЛЕДСТВИЕ 1 (обобщенная формула бинома Ньютона для

слагаемых) .

_____

ЗАМЕЧАНИЕ 1 (правило суммы) Пусть есть

подмножества множества . Обозначим число элементов

(длину, площадь) множества . Тогда

.

◄ Обоснуем замечание при .

.

Теперь воспользуемся этой формулой.

. ►

 

ЗАМЕЧАНИЕ 2 (правило произведения) Если множества

конечны, то число элементов декартова произведения

конечно и вычисляется по формуле

.

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-12-29 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: