![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
С помощью диаграммыСтр 1 из 17Следующая ⇒
Композиция машин Тьюринга
Для организации такой работы достаточно построить объединенную таблицу машины Тьюринга, приписав к первой таблице вторую (справа) и заполнив пустые клетки первой таблицы командой перехода к начальному состоянию второй программы. f(x)=(x+1)*2
Итерация (повторение) машин Тьюринга В этом случае повторяем выполнение одной и той же команды конечное число раз. По окончании первого выполнения на ленте остается промежуточный результат необходимый для второго выполнения и т.д. Для обеспечения второго и последующих выполнений необходимо в некоторые пустые клетки таблицы вписать команду перехода на начало. Во все пустые клетки эту команду вписывать нельзя, так как измененная таким образом программа не сможет заканчиваться. f(X)=X+L eeeeX*Leeeee
3) Алгорифмы Маркова (нормальные алгорифмы) используются для представления алгоритмов, преобразующих одну цепочку символов (исходные данные) в другую (результат). Отличие алгорифмов Маркова в том, что каждый шаг преобразования позволяет выполнить замену не одного символа, а целого слова в исходной цепочке. Если применив алгоритм Замены выполняются в соответствии с заданным правилом, которые и будут определять алгоритм. Такой алгоритм называется вербальным. Расширим алфавит Если такое правило срабатывает, то в исходной строке отыскивается подстрока Для определения алгоритма нужно задать не одно правило, не одну формулу подстановки, а множество, причем необходимо определить порядок их применения. Для этого вводится еще одно понятие схемы алгоритма. Схемой – называется слово в расширенном алфавите, имеющее вид Если в строке, которая преобразуется алгорифмом встречается левая часть какой-то формулы Если какая-то подстановка действует на исходную строку, причем левая часть встречается в строчке многократно, то формула подстановки применяется один раз. Причем применяется к самому левому вхождению. При заменах могут использоваться пустые строки Если в схеме используется несколько правил, в которых правые части совпадают, а левые части являются подстроками, которые можно объединить в какое-то множество, то пишут
Пустая строка может встречаться и в левой части. Если есть такие правила, то пустота замениться слева. В этом случае при составлении схемы, нужно думать о том, чтобы алгоритм был применим. Каким образом алгоритм завершает работу? Есть несколько вариантов: 1. Не применима ни одна подстановка в схеме (не действует на полученную строку) 2. Выбирается формула подстановки вида:
4) При разработке алгоритма (программы) встает несколько вопросов: 1) Является ли задача алгоритмические вычислимой, т.е можно ли построить алгоритм для ее решения. Каждую задачу, ее решение можно рассматривать как функции, в которой исходные данные преобразуются в результат. Если мы можем построить метод этого преобразования, формализовать его, то такая функция является вычислимой 2) Если функция вычислима, как построить алгоритм? Попробуем построить алгоритм: 1. Определим базовый набор функций, для которых уже построена машина Тьюринга. Предположим, что все функции преобразуют целые числа в целые числа.
Обозначим этот базовый набор за 2. В базовом наборе функций определим основные операции. Операции получают функции (а не значения функций) в качестве операндов и дают в результате новые функции. Эти операции также должны быть очевидны с математической точки зрения – не должно возникать сомнения в том, что из вычислимых функций с помощью операций получаются вновь вычислимые функции. Последовательно применяя операции из к множеству функций из Обозначим набор этих операций
|