Любой алгоритм можно преобразовать в машину Тьюринга icon

Любой алгоритм можно преобразовать в машину Тьюринга



НазваниеЛюбой алгоритм можно преобразовать в машину Тьюринга
Дата конвертации22.05.2013
Размер152.32 Kb.
ТипДокументы
источник
1. /Экзамены-2/АлгоритмВопросы.doc
2. /Экзамены-2/АлгоритмТеорема.doc
3. /Экзамены-2/БилГраф.doc
4. /Экзамены-2/Задачи-МТ.doc
5. /Экзамены-2/Тест 1-25.doc
6. /Экзамены-2/ЭкзБилДисМат2.doc
7. /Экзамены-2/ЭкзГраф.doc
8. /Экзамены-2/задачи по графом 2007.doc
Алгоритм: определение и основные свойства. Классические машины Тьюринга. Тезис Тьюринга
Любой алгоритм можно преобразовать в машину Тьюринга
Алгоритм Зыкова
Этюд Реализация на машине Тьюринга задачи сортировки слова по возрастанию в алфавите {0,1,2}. Этюд
Тест Этюд Реализация на машине Тьюринга задачи сортировки слова по возрастанию в алфавите {0,1,2}. Этюд
Задача. Экзаменатор
1. Дайте полный список проведенных игр, соответствующий графу на рис. 3
Вопросы и задачи

  1. Алгоритм: определение и основные свойства.

Алгоритм - это точное предписание о выполнении в некотором порядке системы операций, определяющих процесс перехода от исходных данных к искомому результату для решения всех задач некоторого данного типа. Это неформальное определение алгоритма, известное еще со времен Аль Хорезми (IX век). Предписание считается алгоритмом, если оно обладает следующими свойствами

  • определенностью, то есть общепонятностью и точностью, не оставляющими место произволу;

  • массовостью, то есть возможностью исходить из меняющихся в известных пределах значений исходных данных;

  • результативностью, то есть направленностью на получение искомого результата;
    элементарностью шагов, на который разбивается алгоритм.

  1. Классические машины Тьюринга


Первый важный и достаточно широкий класс алгоритмов был описан Тьюрингом и Постом в 1936-1937гг. Алгоритмы этого класса осуществляются особыми машинами, называемыми в настоящее время машинами Тьюринга-Поста или просто машинами Тьюринга. Машины Тьюринга копируют в существенных чертах работу человека, вычисляющего по заданной программе, и часто рассматриваются в качестве математической модели для изучения функционирования человеческого мозга.


    1. Тезис Тьюринга

Тезис Тьюринга заключается в том, что любой алгоритм можно преобразовать в машину Тьюринга.



    1. Машина Тьюринга: принцип действия, описание работы


Под одноленточной машиной Тьюринга понимают такое кибернетическое устройство, которое состоит из следующих элементов:

  • бесконечной ленты, разделенной на ячейки;

  • управляющей головки, способной читать символы, содержащиеся в ячейках ленты, и писать символы в эти ячейки;

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

  • механического устройства управления, обеспечивающего перемещение головки относительно ленты

  • функциональной схемы — области памяти, содержащей команды (программу) машины Тьюринга, доступной только по чтению

    1. Построение алгоритмов для реализации на машинах Тьюринга


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

    1. Универсальные машины.

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

Универсальность некоторой машины Тьюринга выражается в её способности путём подходящего кодирования выполнить любое вычисление, которое могла бы выполнить любая заданная машина Тьюринга. Однако к этому, несомненно, надо присоеденить то условие, что кодирование должно быть в некотором смысле простым. В самом деле, нет особой выгоды считать универсальной машину Тьюринга, у которой кодирование, по существу, требует работы другой универсальной машины. Отсюда возникает задача явного определения универсальной машины Тьюринга.


Кодирование программы машины Тьюринга.

Построение универсальной машины Тьюринга

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


    1. Первая теорема Шеннона.


Эквивалентность машин: машина В эквивалентна машине А, если в соответствующие такты их работы лента машины В содержит всю информацию о ленте машины А. Машина В работает гораздо медленнее, т.к. каждый такт А она моделирует несколькими тактами, поэтому мы говорим о соответствующих тактах. Если А остановится, то В тоже остановится и будет содержать всю информацию о машине А.


Теорема Шеннона №1

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


    1. Вторая теорема Шеннона.


Теорема Шеннона №2.

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


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


Самоанализирующие машины Тьюринга


Машину Тьюринга, способную обрабатывать свою таблицу, мы назовем самоананализирующей машиной Тьюринга. Самоанализирующая машина- это машина, которая в качестве кода читает свой собственный код (читает саму себя).


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


ТЕОРЕМА: Задача об остановке произвольной машины Т при обработке произвольного слова t алгорифмически неразрешима.


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


Алгорифмическая неразрешимость задачи о печатании символа точно один раз.


ТЕОРЕМА: Задача о печатании данного знака машины на чистой ленте точно один раз алгоритмически неразрешима.


Алгорифмическая неразрешимость задачи о печатании символа бесконечно много раз.


ТЕОРЕМА: Задача о печатании данного знака машины на чистой ленте бесконечно много раз алгоритмически неразрешима.


Алгорифмическая неразрешимость задачи о печатании символа хотя бы один раз.


ТЕОРЕМА: Задача о печатании данного знака машины на чистой ленте хотя бы один раз алгоритмически неразрешима.


Тезис Маркова. Нормальные алгоритмы (не закончено).


Тезис Маркова: любой вычислительный процесс можно преобразовать в нормальный алгоритм.


Алгоритмы Маркова


Основная операция при работе алгоритмов Маркова – это переработка слов в некотором алфавите. Эта переработка заключается в производстве некоторого количества замен определенных последовательностей символов. Эти замены совершаются в СТРОГО определенном порядке, а именно: после каждой замены алгоритм читается с самого начала, а слово анализируется с самого первого символа. В отличие от машин Тьюринга, алгоритмы Маркова выполняются без какого – либо устройства, осуществляющего движения и имеющего внутреннюю память. В данном случае мы можем оперировать только ленточными знаками. Сама лента в этом случае не разделяется на строгие ячейки, а имеет гибкую основу, что позволяет ей растягиваться и сжиматься исходя из того, увеличивается ли в слове число символов или уменьшается.


Преобразование машин Тьюринга в нормальные алгоритмы.


Лекция 6.

Понятие эффективной перечислимости. Перечисление машин Тьюринга и алгоритмов Маркова. Эффективное распознавание и теорема Поста. Перечисление останавливающихся машин.


Понятие эффективной перечислимости

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


Эффективная перечислимость машин Тьюринга


ТЕОРЕМА: Множество машин Тьюринга эффективно перечислимо.


Эффективная перечислимость нормальных алгоритмов


ТЕОРЕМА: Множество алгоритмов Маркова эффективно перечислимо.


Теорема Поста (Эффективная распознаваемость подмножества эффективно перечислимого множества)


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


ТЕОРЕМА: Если множество В эффективно перечислимо, то подмножество А эффективно распознается в В тогда и только тогда, когда А и В-А оба эффективно перечислимы.


Эффективная перечислимость останавливающихся машин Тьюринга и невозможность эффективного перечисления не останавливающихся машин Тьюринга.


ТЕОРЕМА: Множество останавливающихся машин Тьюринга эффективно перечислимо.


ТЕОРЕМА: Множество не останавливающихся машин Тьюринга невозможно эффективно перечислить.


Лекция 7.

Сведение числовых систем к натуральным числам. Равномощные множества и кардинальные числа. Парадокс Галилея и трансфинитные числа. Конечные, счетно-бесконечные и несчетные множества чисел


Сведение числовых систем к натуральным числам.


Лекция 8.

Счетность множества натуральных, целых, рациональных и алгебраических чисел. Несчетность множества трансцидентных, действительных и комплексных чисел.

Вычислимые действительные числа. Вычислимость алгебраических и существование вычислимых трансцидентных чисел. Невычислимые числа.


Теорема Кантора (забыла включить в лекцию№7)

Для любого кардинального числа α справедливо α<2α


Множество всех подмножеств данного множества называется булеаном данного множества.


Каждому подмножеству М сопоставим его характеристическую функцию:

f M(x)=1 если x принадлежит М

f M(x)=0 если x принадлежит А но не принадлежит М

Всего характеристических функций: 2|Α|


α =|Α|

2α=| {0,1}Α |


Счетность множества натуральных чисел


Счетность множества целых чисел


Счетность множества рациональных чисел


Счетность множества алгебраических чисел


К вопросу о приведении числовых систем к натуральным числам (добавить в лекцию №7)


Метод Дедикинда.

Действительное число: сечение множества рациональных чисел, т.е. упорядоченная пара двух множеств рациональных чисел (А, В).

Каждое число множества А меньше каждого числа множества В, а в сумме они составляют все множество рациональных чисел.

Например зададим √2 = (А,В)

А = }


B = }








A √2 B

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


Метод Вейштрасса

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


Метод Кантора

Действительное число – предел бесконечной систематической дроби.

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


Несчетность множества действительных чисел


Множество действительных чисел обозначается латинской буквой R.


Теорема: Множество R действительных чисел несчётно.


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


Счетность множества вычислимых действительных чисел.


Существование вычислимых трансцидентных чисел. Невычислимые числа.


Вычислимость рациональных чисел. Вычислимость алгебраических чисел.


Лекция 9.

Несчетность множества арифметических функций. Вычислимые арифметические функции. Невычислимые функции. Невозможность эффективного перечисления и сравнения вычислимых функций.


Арифметическая функция- функция определенная на множестве натуральных чисел и принимающая натуральные значения.


Несчетность множества арифметических функций.


Теорема: Множество арифметических функций n-переменных несчетно.


Вычислимые арифметические функции


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


Счетность множества вычислимых арифметических функций


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


Невозможность эффективного перечисления ВАФ.

Теорема


Множество вычислимых арифметических функций n-переменных не поддается эффективному перечислению.


Невычислимые функции.


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


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


Невозможность эффективного сравнения вычислимых арифметических функций.


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

Теорема


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


Лекция 10.

Несчетность множества частичных арифметических функций. Вычислимые частичные арифметические функции и их эффективное перечисление. Невычислимые частичные функции. Теорема Черча.


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

Пример:

  1. f(n) = n – 1 : {1, 2, …}  N;

  2. f(n) = 1 – n : {0, 1}  {0, 1}.

2 крайних случая множества частичных арифметических функций f(n): M  N:

  1. M = N  M  N. Все остальные частичные арифметические функции имеют точки неопределенности;

  2. Нигде неопределенные функции от некоторого числа переменных. M = .

f(n) = 0 – (n + 1).


Несчетность множества частичных арифметических функций.

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


Эффективная перечислимость вычислимых частичных функций.


Частичная вычислимая арифметическая функция (ЧВАФ)– это функция, для которой существует алгоритм вычисления ее значения в любой точке определенности.


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


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


Теорема. Невозможно эффективно распознать вычислимые арифметические функции среди вычислимых частичных арифметических функций..


Теорема Черча (невозможность эффективного распознавания точек неопределенности вычислимой частичной функции).


Теорема. Невозможно эффективно распознать точки неопределенности вычислимой частичной арифметической функции.


Лекция 11.

Примитивно-рекурсивные функции и базис Клини. Примитивная рекурсивность суммы и факториала.


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


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

Базис Клини состоит из

  • трех простых функций

  • двух разрешенных операций


3 функции:

1) функция следования: S(x) = x' = x+1, где x’ – число, непосредственно следующее за натуральным числом х. Например, 0’ = 1, 1’ = 2, …

n

2) функция тождества: Ui (x1,…,xn) = xi , где n – кол-во переменных, а i – по какой переменной берется тождество. Функция тождества – функция, равная одному из своих аргументов. Например, U23(x,y,z) = y.

n

3) функция константа: Cq (x1,…,xn) = q, где n – число переменных, q – значение, которое принимает функция. Функция константа принимает всюду одно значение. Например, C23(16, 9, 10) = 2.


2 операции:


1) рекурсия R


Если мы имеем функцию одной переменной f(x) то схема рекурсии называется «рекурсия без параметров» и задается системой уравнений:

f (0) = q

f (x') = χ [f (x), x]

Функция, заданная такими уравнениями, кратко задается схемой вида Rq ( χ ).

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


Если мы имеем функцию нескольких переменных f(x1, x2,…, xn) то схема рекурсии называется «рекурсия с параметрами» и задается системой уравнений:

f (0, x2,…, xn) = Ψ (x2,…, xn)

f (x'1, x2,…, xn) = χ (f(x1,…, xn), x1,…, xn)

Функция, заданная такими уравнениями, кратко задается схемой вида Rn (Ψ, χ)


2) суперпозиция S:

Пусть заданы m каких либо частичных арифметических функций f1, f2,…fm от одного и того же числа n переменных, определенных на множестве А со значениями в множестве В. Пусть на множестве В задана частичная функция Ф от n переменных, значения которой принадлежат множеству С. Введем теперь частичную функцию g от n переменных, определенную на А со значениями в С, полагая по определению

g(x1,…, x n) = Φ (f1 (x1,…, x n), f2 (x1,…, x n),…, f m (x1,…, x n ))

для произвольных x1,…, x n из А. Говорят, что функция g получается операцией суперпозиции или подстановки из функций f1, f2,…fm. Обозначается эта операция буквой S с двумя индексами: верхний (n) показывает от скольких переменных зависят внутренние функции fi (x1,…, x n), а нижний (m) – количество самих функций f1, f2,…fm

n

g(x1,…, x n) = S m (Φ, f1, f2,…, f m),

При этом функция Ф при подсчете внутренних функций не учитывается.

Пусть например заданы обычные функции + и *. Некая функция от


Геделева нумерация и эффективная перечислимость примитивно-рекурсивных функций.


Теорема: Примитивно-рекурсивные функции эффективно перечислимы


Лекция 12.

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


Общерекурсивные и частично-рекурсивные функции.


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

Рассмотрим равенство f(х)=g(x), где f(х) и g(x) некоторые функции. Когда говорят, что это равенство есть уравнение, то это означает, что равенство рассматривается как неопределенное высказывание, при одних значениях х истинное, при других ложное.

Определение. Функция является обще-рекурсивной, если она определена посредством ряда уравнений некоторого типа.


Тезис Черча: класс алгоритмически (или машинно) вычислимых частичных числовых функций совпадает с классом всех частично рекурсивных функций.

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


Расширенный базис Клини. Частичная рекурсивность разности.


Определение. Частичная арифмитическая функция f называется частично рекурсивной, если она может быть получена из простейших функций O, S, Umn конечным числом операций подстановки, примитивной рекурсии и минимизации.


Геделева нумерация и эффективная перечислимость частично-рекурсивных функций.


Частичная рекурсивность нигде не определенной функции и функции, определенной в одной точке.


1) Нигде неопределенная функция .

Построим рекурсивное уравнение:



Результат операции минимизации неопределен даже для точки х=0.


2) Функция, определенная в одной точке, .

Построим рекурсивное уравнение:



Результат операции минимизации определен только для точки х=0, при остальных значениях x вычисление (подбор нужного значения z) никогда не будет закончено.


Лекция 13.

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


Рекурсивные функции и невозможность их эффективного перечисления.


Теорема: рекурсивные функции не поддаются эффективному перечислению.


Невозможность эффективной распознаваемости примитивно рекурсивных функций среди рекурсивных


Теорема: Примитивно-рекурсивные функции не поддаются эффективному распознаванию среди рекурсивных функций.


Невозможность эффективной распознаваемости рекурсивных функций среди частично рекурсивных функций.


Теорема: Рекурсивные функции не поддаются эффективному распознаванию среди частично рекурсивных функций.


Нерекурсивные функции


Нерекурсивной называется функция, значение которой нельзя вычислить несмотря на то, что в данной рассматриваемой точке сама функция определена.

Например, зададим функцию f(x) следующим образом


f(x)=1 если машина Тьюринга Tx останавливается на чистой ленте

f(x)=0 если машина Тьюринга Tx никогда не остановится на чистой ленте


Значения везде определены (0 или 1), но вычислены быть не могут, иначе бы это означало что решена задача об остановке произвольной машины Тьюринга.




Похожие:

Любой алгоритм можно преобразовать в машину Тьюринга iconАлгоритм: определение и основные свойства. Классические машины Тьюринга. Тезис Тьюринга
Машина Тьюринга: принцип действия, описание работы. Построение алгоритмов для реализации на машинах Тьюринга
Любой алгоритм можно преобразовать в машину Тьюринга iconКонкурс «Мой помощник компьютер» Этап II. Задача Даны два натуральных числа n и m
Необходимо построить машину Тьюринга, которая на ленте оставит сумму чисел n и m (в унарной системе). Конечное положение автомата...
Любой алгоритм можно преобразовать в машину Тьюринга iconКонкурс «Мой помощник компьютер» Этап II. Задача 1
Входное слово состоит только из + и. Автомат (каретка) находится где-то слева от входного слова. Необходимо построить машину Тьюринга,...
Любой алгоритм можно преобразовать в машину Тьюринга iconКонкурс «Мой помощник компьютер» Этап II. Задача Дано натуральное число
Дано натуральное число n в восьмеричной системе счисления. Необходимо построить машину Тьюринга, которая увеличивала бы заданное...
Любой алгоритм можно преобразовать в машину Тьюринга iconКонкурс «Мой помощник компьютер» Этап II. Задача Дано натуральное число n
Необходимо построить машину Тьюринга, которая дописывает вслед за числом букву Ч, если заданное число чётное, и – букву Н, если нечётное....
Любой алгоритм можно преобразовать в машину Тьюринга iconУстройство Машины Тьюринга
В состав Машины Тьюринга входит бесконечная в обе стороны лента, разделённая на ячейки, и управляющее устройство, способное находится...
Любой алгоритм можно преобразовать в машину Тьюринга iconАрхивация файлов Файлы и файловая система
Действительно, если внимательно посмотреть любой текст, то можно заметить, что такие буквы «а» и«о», встречаются в нем гораздо чаще...
Любой алгоритм можно преобразовать в машину Тьюринга iconСравнение Широкий — узкий
Раскрась машину, которая едет по широкой дорожке, зеленым цветом, а машину, которая едет по узкой, — красным. Какая машинка большая,...
Любой алгоритм можно преобразовать в машину Тьюринга iconСистемы распознавания текста Технология обработки текстовой информации
Текст можно будет читать и распечатывать, но нельзя будет его редактировать и форматировать. Для получения документа в формате текстового...
Любой алгоритм можно преобразовать в машину Тьюринга iconОператоры присваивания, ввода и вывода информации используются в линейном алгоритме
Линейный алгоритм алгоритм, в котором команды выполняются один раз последовательно друг за другом (линейный алгоритм)
Любой алгоритм можно преобразовать в машину Тьюринга iconКонтрольная работа по теме «Алгоритмы» Вариант 1 Дать определения понятиям: алгоритм, циклический алгоритм > Найдите значение Х после выполнения алгоритма 1, если х=5
Выполнить алгоритм Занести значения переменных, изменяющихся в ходе выполнения алгоритма в таблицу
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©lib2.podelise.ru 2000-2013
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы