Всего на сайте:
236 тыс. 713 статей

Главная | Информатика

Задачи.  Просмотрен 77

Используя элементарные машины и операции над машинами, постройте:

а) машину Тьюринга, которая по записи набора чисел x1, х2, ..., хn на ленте выдает в качестве результата набор чисел x1, х2, ..., хn, 2, воспринимаемый в стандартном положении; Решение: С◦A◦A

б) машину Тьюринга, которая по записи числа на ленте в качестве результата выдает число, увеличенное на единицу и записанное через одну пустую ячейку от данного (иными словами, машину, вычисляющую функцию прибавления единицы f(a) = = а+1). Построить машину Тьюринга означает построить программу машины, а затем проверить, ту ли машину построили, имитируя ее работу для конкретных записей на ленте. При составлении программ для реальных вычислительных машин эту проверку называют отладкой программы. Решение:

Какие операции выполняют машины:

а) . Решение: Справа от данного числа будет две копии этого числа, разделенные одной пустой ячейкой;

б) R2. Решение: Переход вправо через одно число;

в) Rk, k³1. Решение: Переход вправо через k чисел;

г) Lk, k³1 Решение: Переход влево через k чисел;

д) С°А5 Решение: Запись 5 справа от текущего числа;

е) T1°A4 Решение: Выдать число, увеличенное на четыре и записанное через одну пустую ячейку от данного.

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

Составьте программу машины: а) С°А3; б) Т1°А4.

Составьте программу машины Тьюринга Тx+y, которая по записи набора чисел х, у выдает запись числа, являющегося их суммой, т. е.

вычисляющей функцию S(x, y) = x+y. Решение: , где через Сm обозначена машина из примера 11.

5. Машина Тьюринга — математическое понятие алгоритма.[E27]

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

Что есть в каждой машине Тьюринга? Есть три конечных множества A, Q и Т и программа, полностью определяющую работу машины Тьюринга.

Что же представляет собой программа?

Каждой паре вида (si, qi), где siÎА и qiÎQ\{q0}, соответствует тройка (sj, t, qj), где sjÎA, tÎT и qjÎQ (q0 не участвует в парах (si, qi), так как паре (si, q0) уже ничего не соответствует, машина останавливается в заключительном состоянии q0).

[E28]

Множество всех пар вида (si, qi), где siÎA и qiÎQ\{q0}, называется произведением множеств А и Q\{q0} и обозначается А´Q\{q0}. Аналогично, множество всех троек вида (sj, t, qj), где sjÎA, tÎT и qjÎQ, называется произведением множеств А, Т и Q и обозначается А´Т´Q.

[E29]

Таким образом, программа машины Тьюринга представляет собой функцию с областью определения А´Q\{q0}, принимающую значения из множества А´Т´Q, или отображение первого множества во второе: А´Q\{q0}®A´T´Q

[E30]

Машиной Тьюринга (МТ) называется система вида (A, s0, Q, q1, q0, T, t),

где А - конечное множество - алфавит МТ,

s0ÎA и называется пустой буквой алфавита,

Q - конечное множество, элементы которого называются состояниями МТ (Q - множество состояний МТ),

q1ÎQ, q1 - начальное состояние МТ,

q0ÎQ, q0 - пассивное или заключительное состояние МТ,

Т={Л, Н, П} - множество сдвигов МТ,

t :А´Q\{q0}®A´T´Q, t - программа МТ.

[E31]

Нетрудно убедиться в том, что в этом определении фигурируют только математические и логические термины (или символы): множество, конечное множество, элемент множества, отношение принадлежности (Î), функция (®), произведение множеств, есть (—), равно ( = ). И никакие другие, нематематические или нелогические понятия в приведенной формулировке не используются.

 

Машина Тьюринга перерабатывает слова в алфавите машины согласно программе этой машины.

[E32]

Какую бы МТ, имеющую алфавит A={s0, s1, ..., sk}, состояния q0, q1, ..., qp и программу t, мы ни взяли, можем считать, что имеется алгоритм, исходными объектами, промежуточными и окончательными результатами которого являются слова в алфавите А. Предписанием, задающим этот алгоритм, является программа t.

[E33]

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

[E34]

Проиллюстрируем основные свойства алгоритмов на примере МТ.

Предыдущая статья:Задача 11. Следующая статья:Всякий алгоритм может быть задан посредством МТ
page speed (0.014 sec, direct)