Функции для построения схем(программ) машин Тьюринга

Конструирование машин Тьюринга

Начальные конфигурации машины Тьюринга

Применение машин Тьюринга к словам

Задания к выполнению работы

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

Состояние машины

2. Убедиться, что машина с алфавитом и программой

Состояние машины

каждое слово длины алфавита перерабатывает в слово длины r (r – остатокот деления числа на 3).

3.Рассмотреть, как работает машина Тьюринга, заданная функциональной схемой (табл.10.5),

Таблица 10.5

Состояние машины Тьюринга	Последовательность букв внешнего алфавита (слова)

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

Таблица 10.6

№ варианта	Начальная конфигурация	№ варианта	Начальная конфигурация

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

Таблица 10.7

№ варианта		№ варианта		№ варианта

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

3. Построить машину Тьюринга, которая применима ко всем словам в алфавите и делает следующее: любое слово , где или (), преобразует в слово .

4. Построить машину Тьюринга для вычисления функции

5. Построить машину Тьюринга для вычисления функции

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

Дата добавления: 2017-02-01