дзержинский и воронцов 2

4)Строится автоматная таблица для полученного логического

автомата.

5)Строится таблица управления памятью по полному автомату

Мура.

6)Записываются канонические уравнения и уравнения для управляющих памятью функций.

7)Функции реализуются в виде схем.

Примеры:

Машина Тьюринга

Опр.: Машина Тьюринга Т – это пятерка объектов Т={A,Q,F,G,H}

A – входной и выходной алфавит, Q – алфавит состояний, F – функция выхода, G – функция перехода, H – функция управления

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

Имеется бесконечная лента, разделенная на ячейки. В ячейках выписывается либо пустой символ …, либо другая буква алфавита A.

На каждом шаге машина прочитывает входную букву, переходит в новое состояние согласно ф.G, печатает вместо прочитанной буквы новую согласно ф.F и сдвигается вправо, влево или остается на месте в зависимости от ф.H.

Способы задания машины Тьюринга.

1)Автоматная таблица

На пересечении i-той строки (аi) и j-того столбца (qj) записывается новая буква а’, новое состояние q’ и управляющий символ h

2)Программа

Запись aiqj – a’q’h называется командой машины Тьюринга. Она описывает работу Т в один из множеств моментов времени. Список какого-либо множества команд будем называть программой или списком. Программа задает работу машины Тьюринга.

Замечания:

Команды не обязательно содержат в левых частях все возможные сочетания (a, q), а только те, которые реально встречаются в процессе работы.

Утверждение 1

Головка машины Тьюринга есть конечный автомат. Из описания

13

машины Т следует, что головку машины можно рассматривать как конечный автомат М, у которого А=А, Q=Q, B=Ax{R,L,S}, функции F’(a,q), G’(a,q) определяются из программы работы машины Тьюринга:

Утверждение 2

Функционирование любого конечного автомата можно смоделировать на машине Тьюринга. Пусть конечный автомат М={A,Q,B,G,F}.

Утверждение 3

Возможности машины Тьюринга больше чем у конечного автомата.

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

Вычисления на машинах Тьюринга

Определение

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

Определение

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

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

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

На ленте натуральное число х будет записываться массивом из х единиц … Числа на ленте будем разделять символом «*», если пустой символ … , то это ноль.

Рассмотрим произвольную функцию y=f(x1…xn), где xi – целые

14

неотрицательные числа, y – принимает целое неотрицательное значение.

Функция f(x1…xn) называется вычислимой по Тьюрингу, если существует машина Тьюринга, работающая следующим образом: для любой совокупности чисел x1,x2…xn, для которых функция f определена, машина Тьюринга, начав работу из начальной конфигурации q01x*1x2…1xn, заканчивает работу конфигурацией q01y, где y=f(x1…xn). Если f на совокупности x1..xn не определена, то машина Тьюринга работает бесконечно.

Вычислимость суперпозиции:

Пусть заданы две функции: y=f(x) и z=g(y), причем z определена на области значений функции f, тогда функция z=g(f(x)) называется суперпозицией функций f и g или композицией.

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

Доказательство. Чтобы написать программу для композиции, надо объединить обе программы и сделать следующие изменения: во всех командах первой программы для функции f, где встречается заключительное состояние q(z1), его надо заменить на начальное состояние второй программы q02.

Вычислимость (разветвления) условного перехода.

Определение. Пусть x1,x2…xn символы переменных произвольной природы. n-местным предикатом P(x1…xn) называется высказывание об этих переменных, которое для каждого набора значений переменных либо не определено, либо истинно, либо ложно.

Определение: областью определения предиката Р (х1, …,хn) называется совокупность всех наборов х1 ...хn, для которых предикат Р (х1…,хn) либо И, либо Л.

Область истинности – множество всех наборов х1 …..хn для которых Р (х1,

….,хn) = И.

Характеристической функцией предиката Р называется функция

15

1, если Р (х1, ….,хn) =И

Хр(х1, …..,хn)

0, если Р (х1, ….,хn) =Л

Р(х1,х2) = х1 ≥х2

Определение: Предикат называется вычислимым по Тьюрингу если его характеристическая функция вычислима. Иногда предикат будем считать вычислимым если существует М. Тьюринга приводящая к конфигурации И x1*x2*…*xn,то есть перед первым аргументом стоит символ И. если Р (х1, ….,хn)

= И. .

Теорема: Если функция f1(x1,…,xn),f2(x1,…,xn) и предикат P(x1,…,xn)

вычисляется по Тьюрингу, то и функция

f1(x1,…,xn) если Р (х1, ….,хn) =И

f(x1,…,xn)=

f2(x1,…,xn) если Р (х1, ….,хn) =/\

также вычислима по Тьюрингу.

Вычисление функции f(x1,…,xn) приводит к разветвлению вычисления.

Нужно доказать, что существует машина Тьюринга вычисляющая это разветвление. Будем считать что алфавиты состояний исходных машин не пересекаются. Программу искомой машины составим из программ исходных машин внеся изменения только в программу для Машины Тьюринга вычисляющей предикат. Те команды где есть конечное состояние Иqzph заменяем на /\q01R (то есть машина переходит к программе для f1),а команды Лqzph заменяем на /\q02R (то есть машина стирает значение «ложь», записывает пустой символ и переходит к программе для f2.

Гёделевская нумерация

Это прием позволяющий любой алгоритм превратить в численный алгоритм, работающий с натуральными числами, объекты любой природы можно закодировать натуральными числами. Пусть существует некоторый алфавит А. Рассмотрим все слова языка А*=множество всех слов в алфавите А. Мы хотим все слова αєА* перенумеровать так чтобы соответствие между словом α и его номером N(α) было взаимно-однозначным. Если α=аi1ai2…ais то номер слова это N(α)=2i1*3i2*…*piss где ps-простые числа. Получим некоторое

16

натуральное число, которое называется его геделевским номером. Это сопоставление каждому слову натуральное число называется первичной нумерацией по Гёделю.

Вторичная нумерация это если есть последовательность слов Π=α1α2…αn тогда этой фразе взаимно-однозначно можно составить одно натуральное число

N(П)=2N(α1)*3N(α2)…PkN(αk)

С помощью третичной нумерации можно занумеровать любой текст.

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

По Гёделевскому номеру однозначно восстанавливается закодированный объект. Это следует из арифметики: всякое натуральное число однозначно разложимо в произведение степеней простых чисел.

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

ЧАСТИЧНО-РЕКУРСИВНЫЕ ФУНКЦИИ

Будем рассматривать функции аргументы и значения которых будут целыми неотрицательными числами.

Функция f(x1,…,xn) называется частичной, если, по крайней мере, на одном наборе значений аргументов она определена.

Введем следующие операции над частичными функциями

I.Операция суперпозиции:

Пусть h(x1,…,xn),g1(x1,…,xm),…,gn(x1,…,xm) - частичная функция. Тогда про функцию f(x1,…,xm)=h(g1(x1,…,xm),…,gn(x1,…,xm)) будем говорить, что она получена из функций h;g1,…,gn при помощи операции суперпозиции.

II.Операция рекурсии (примитивная).

17

Будем говорить, что функция f(x1,…,xn,y) Получена из функций g(x1,…,xn) и h(x1,…,xn,y,z) при помощи операции рекурсии, если значения функции f вычисляются по следующему правилу f(x1,…,xn,0)=g(x1,…,xn,)

f(x1,…,xn,y+1)=h(x1,…,xn,y,f(x1,…,xn,y))

III. Операция минимизации:

Пусть g(x1,…,xn-1,y) – частичная функция, зафиксируем набор

переменных x1,x,…,xn-1,xn И	рассмотрим уравнение	(относительно		y) :
g(x1,…,xn-1,y)=xn
Тогда минимальное значение y удовлетворяющее		этому уравнению ,
обозначим через µ=µg(g(x1,…,xn-1,y)=xn) Очевидно, что			µ есть функция
относительно x1,…,xn-1,xn которая	получена из функции g(x1,…,xn-1,y)		применением	операции

минимизации.

С помощью операции минимизации из функции сложение получается функция вычитание µn=(x+y=z)=z-x;

Среди частичных функций выделим так называемые базисные функции (элементарные).

1)Нуль-функция O(x)=0 при любом x=0,1,2,...

2)функция следования S(x)=x+1 при любом x=0,1,2,...

3)функция выбора Imn(x1,…,xn)=xm , 1≤m≤n

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

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

Если частично-рекурсивная функция всюду определена, то она называется рекурсивной.

18

Примеры: 1) сложение f(x,y)=x+y рекурсивно: берем g(x)=I12(x,y)=x

;h(x,y,z)=S(z): тогда

2)Умножение x*y рекурсивно, так как если g(x)=O(x); h(x,y,z)=x

3)f(x,y)=xy рекурсивна так как,если g(x)=x0=1, h(x,y,z)=x*z

4) Усеченная разность x-y: сначала находим что f(y)=y-1 рекурсивно

g=0 h(y,z)=I12(y,z)=x:

Используя рекурсивные функции x 0 и x-1 строим функцию x-1 по схеме x-0=x : x-(y+1)=(x-y)-1

Нормальный алгоритм Маркова

Задается алфавит А= α1,…, αm -то есть любая конечная система различных символов. буквами называются символы составляющие алфавит. Словом в алфавите наз. любая конечная последовательность букв в этом алфавите.

Пустым словом называется слово, не содержащие ни одной буквы и обозначаемое символом /\. Два конкретных слова αi1… αin и bi1…bim в алфавите А равны если n=m и αik=bik . Все пустые слова считаются равными. Если αi1… αin-слово, состоящие из n букв то n-наз. длинной этого слова. Длинной пустого слова будет число 0.

Рассмотрим два слова: C и D в нек. алф. А. Если слово C является частью слова D,то говорят, что слово C входит в слово D. Процесс преобразования слов, позволяющий из заданного слова получить новые слова задается с помощью допустимых подстановок. Подстановка-это пара слов в рассматриваемом алфавите P→Ф. Эту подстановку можно применять к некоторому слову Р этого алфавита следующим способом : если в слове R имеется одно или несколько включений слова Р, то любое из этих включений может быть заменено словом Q.

19

А.А.Марковым было дано точное	математическое определение
нормального алгоритма.

Задается алфавит А и фиксируется схема подстановок. Алгоритм предписывает, исходя из произвольных слов R в алфавите А, просмотреть формулы подстановок в том порядке, в котором они заданы в схеме, разыскивая формулу с левой частью входящей в R. Если такой формулы не найдется, то процесс обрывается. В противном случае берется первая из таких формул и делается подстановка ее правой части вместо первого вхождения ее левой части в слово R, что дает новое слово R1 в алфавите А. После выполнения первого шага приступают ко второму шагу, отличающемуся от первого только тем, что роль R играет R1 Далее делают аналогичный третий шаг и так далее, до тех пор, пока не придется оборвать процесс. Оборваться же он может лишь двумя способами: во первых, когда мы получим такое слово Rn, что ни одна из левых частей формул схемы подстановок не будут в него входить;

Во вторых, когда при получении слова Rn нам придется применить “последнюю” формулу из подстановок “так называемую «заключительную»”. Она обычно выделяется точкой или маленьким кружочком стоящим перед правой частью

Различные нормальные алгоритмы отличаются друг от друга лишь алфавитами и системами допустимых подстановок. Чтобы задать какой-либо нормальный алгоритм достаточно задать алфавит и систему подстановок. Нормальный алгоритм определяет отображение F: A*→A* множеств слов в алфавите А.

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

Пример:

А= 1,*

1) *→/\ 2)1→o1

P→oQ

Определение алгоритма:

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

20

Анализ известных в математике алгоритмов дал возможность выявить характерные его свойства.

1.Дискретность: Выполнение алгоритма состоит из отдельных шагов. Каждый шаг обязательно завершается.

2.Элементарность шагов. Выполнение каждого шага работы алгоритма должно быть простым и не требовать какой-либо изобретательности от исполнителя.

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

4.Направленность: Должно быть указано, что надо считать результатом алгоритма.

5.Массовость: Исходные данные для алгоритма могут выбираться из заранее фиксированных множеств возможных исходных данных. Однако, это множество бесконечно. То есть алгоритм служит для решения целого класса задач.

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

То есть Тьюрингов подход к ответу на вопрос «Что такое алгоритм?» очень прост «Алгоритм – это машина Тьюринга».

Вычислимость по Тьюрингу частично-рекурсивных функций

Утверждение: Любая частично-рекурсивная функция вычислима по Тьюрингу. И обратно: функция, вычислимая по Тьюрингу, является частичнорекурсивной.

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

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

Утверждение: класс функций, вычислимых по Маркову, совпадает с классом функций, вычислимых по Тьюрингу, и следовательно, совпадает с классом частично-рекурсивных функций.

Возникает естественный вопрос «Существуют ли алгоритмически неразрешимые по Тьюрингу проблемы?» Имея точное определение

21

вычислимости, удалось доказать, что некоторые проблемы неразрешимы.

Например:

1.Теорема Черча о неразрешимости логики предикатов: Не существует алгоритма, который для любой формулы логики предикатов устанавливает общезначима она или нет.

2.Проблема остановки неразрешима: Не существует никакого общего алгоритма, позволяющего установить, остановится ли некоторая конкретная программа (на любом языке программирования) ,запущенная после введения в нее некоторого конкретного набора данных. Смысл этого утверждения для теоретического программирования очевиден: не существует совершенно общего метода проверки программ на наличие в них бесконечных циклов.

Исчисление высказываний

Под высказыванием понимают повествовательное предложение, о котором можно сказать одно из двух – истинно оно или ложно. То есть высказывание – это утверждение, которое может быть только истинно или ложно.

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

Из элементарных высказываний строятся более сложные высказывания с помощью логических связок «не», «и», «или», «то же, что» («эквивалентно»), «из…..следует….» («….влечет…»)

Связки логики высказываний представляют функции алгебры логики: отрицанием высказывания А называется высказывание С ¬А Ᾱ, которое истинно только тогда, когда А ложно. Конъюнкцией высказывай А и В называется высказывание С, которое истинно только тогда, когда А и В истинны С=А/\В. Дизъюнкцией высказываний А и В называется высказывание С, которое ложно тогда и только тогда, когда оба высказывания ложны С=АVB. Импликацией высказываний А и В называется высказывание С, которое ложно тогда и только тогда, когда А истинно, а В ложно С=А→В.

Эквиваленцией высказываний А и В называется высказывание С, которое истинно только тогда, когда значения высказываний А и В совпадают. С=А~В (А=А↔В).

С помощью связок можно получить составные высказывания, которым соответствует формула.

22