63. Характерные черты алгоритма

1. Алгоритм имеет дело с данными: исходные данные преобразуются в промежуточные и, далее, в выходные данные. Данные должны принадлежать достаточно широкому классу, так как алгоритм предназначается для решения задач определенного класса (а не одной конкретной задачи), но класс используемых данных ограничен

2. Предполагается наличие у алгоритма памяти

3. Алгоритм состоит из конечного числа правил, каждое из которых выполняется за конечное время.

4. Правила связаны причинно-следственной связью, каждое правило однозначно определяет приемника, вход приемника определяется входом предшественника

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

64. Элементы модели алгоритма

1. Данные

2. Память

3. Набор элементарных правил

4. Организация элементарных правил

5. Механизм, обеспечивающий реализацию заданных элементарных правил в соответствии с их организацией.

65. Основные предположения об элементах модели алгоритма

1. Каждый объект является словом в некотором конечном алфавите

2. Память состоит из одинаковых ячеек, каждая из которых может содержать один символ алфавита. Память может быть бесконечной.

3. Набор элементарных правил конечен.

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

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

66. Устройство машины Тьюринга

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

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

Механизм, обеспечивающий работу машины Тьюринга, состоит из читающей\пишущей головки, которая:

1. В каждый данный момент времени может обрабатывать только одну ячейку ленты

2. За один такт работы Машина Тьюринга может переместиться на одну ячейку налево\направо или остаться на прежнем месте.

– алфавит внутренних состояний. В каждый момент времени Машина находится в одном из состояний.– стоп состояние.

Команды имеют вид:

, гдеT– один из символовL,R,S

Если Машина встречает в ячейке, то:

1. В текущей ячейке будет заменен на

2. Головка передвинется в направлении T

3. Состояние переведено в

67. Комбинации машин Тьюринга: композиция

Пусть имеются две Машины Тьюринга: . Лента обрабатывается, которая выдает заключительное слово и останавливается. Это слово является начальным состоянием, которая обрабатывает ленту до своего стоп-состояния. Заключительное словоможно интерпретировать как заключительное слово, а начальное словокак начальное слово.

Программу можно сконструировать изиследующим образом:

1. Стоп состояние отождествляем с начальным состоянием

2. Пусть – алфавит состояний,– алфавит состояний, то:

   1. Состояния обозначим какдля

   2. Состояния обозначим какдля

   3. обозначаем как

   4. обозначаем как

Полученная машина называется композициейи