4. Машина Маркова

Тезис Маркова: Для любой интуитивно вычислимой функции существует алгоритм, ее вычисляющий. Это что-то сродни Машине Тьюринга в том смысле, что применялось в основном для анализа таких проблем как алгоритмическая разрешимось задач. Суть этих самых алгоритмов Маркова в следующем. Задача для алгоритмов Маркова ставится в виде: найти алгоритм (написать программу) переводящую любую строку S (заданную на некотором алфавите (т.е. наборе символов, которые могут в нее входить)) из некоторого допустимого множества входных строк в строку f(S). Т.е., построить программу - преобразователь строк, выполняющую некое преобразование. Программа на языке алгоритмов Маркова - представляет из себя набор правил. Каждое правило представляет собой замену.

Правило машин Маркова можно проиллюстрировать на примере 1) ab ->cd, 2) ba->dc.

Если во входном слове встречается комбинация ab, то в результате применения правила 1 она меняется на cd.

МТ равносильна М. Маркова. Докажем. Рассмотрим 1 правило.

(*)

Для представления равносильного правила Маркова введем 2 новых обозначения T,Q – произвольный комбинации символов; x – произвольный символ. Запишем следующее правило Маркова:

(**)

Применив к (*) (**) получим

5. Нумерация мт

Существуют понятия:

• У

  Номер МТ

  Входное слово

  ниверсальная МТ – представляет собой некоторую функцию.

F_x(y)

Теорема К.Геделя: положительно целое число можно представить единственным способом в виде произведением простых множителей. Здесь - i-й простой множитель числа А; ni – степень, с которой данный множитель входит в разложение числа А. Пример 126=2¹ * 3² *7¹.

Данная Теорема является уникальной.

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

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

Доказательство. Доказательство проводится методом, предложенным Кантором и называется канторовским диагональным методом.

Теорема. Для любых целых положительных чисел А и В взаимно однозначно определяется число

С=0.5*((А+В)² +3А+В)

Теорема. Число невычислимых функций несчетно.

6. Пример невычислимой функции, построенной по методу диагонализации Кантора.

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

Составим таблицу.

В ячейках – значения функций. Определим новую функцию:

Данная функция принимает значения по диагонали таблицы.

ТЕОРЕМА. Функция является невычислимой. (для нее нет МТ и номера Гёделя)

1	0	1	1	0	0
0	1	1	0	1	0
1	0	1	1	1	1
1	1	1	1	1	1
0	0	0	1	0	0
1	0	1	0	1	1

1 1 1 1 0 1

0 0 0 0 1 0

5	1	5	8
1	2	7	3
8	5	4	2
3	7	6	9

5249 (+1)

63510