Программирование машины Тьюринга

ПРОГРАММИРОВАНИЕ МАШИНЫ ТЬЮРИНГА

Машина, описанная  английским  математиком

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

В.Н.Касаткин

Основные понятия:  

- архитектура и функционирование машины Тьюринга; 

- интуитивное понятие машины Тьюринга; 

- система команд машины Тьюринга; 

- обработка числовой информации в машине Тьюринга; 

- структурная схема машины Тьюринга; 

- функционирование машины Тьюринга. 

ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ  

2§1. Архитектура и функционирование машины 

Тьюринга. Интуитивные понятия  

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

А.И.Попов. Введение в математическую логику

Характеризуя понятие алгоритма,  отмечалось,  что предписание,  задающее алгоритм,  должно быть составлено таким  образом,  чтобы  его  исполнение  было во всех деталях однозначно осуществимо и не  требовало никаких свободно принимаемых решений.  Другими словами,  исполнитель алгоритма должен действовать согласно предписанию со-  вершенно механически,  не вкладывая в свою работу никакой инициа-  тивы,  никакого  изобретательства.  Но обладать таким свойством в  наибольшей степени может машина. В 1936 году английский математик 

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

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

Понятие вычислимой функции,  как и понятие алгоритма, является  интуитивным. Она определена следующим образом: функция называется  вычислимой,  если существует алгоритм для вычисления ее  значений 

(при любых значениях аргумента). 

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

Однако для нас будет несущественным,  что машины  Тьюринга  на  самом деле  не  существует.  Напротив,  для  наглядности мы будем  предполагать ее "как бы существующей" и в процессе изучения маши-  ны Тьюринга,  в частности,  рассматривая вопросы реализации алго-  ритмов,  мы будем пользоваться программной моделью машины Тьюрин-  га,  выполненной для ПЭВМ на языке Pascal. Эта модель поможет нам  в изучении данного материала и сделает работу более наглядной. 

_21.1. Отличительные особенности машины Тьюринга 

Теоретическая машина Тьюринга отличается от  человека-вычисли-  теля и от реальной вычислительной машины следующими моментами: 

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

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

щая в ЭВМ как единичная элементарная операция, здесь сама расчле-  няется на цепочку еще более простых операций. 

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

3. Машина Тьюринга снабжена потенциально бесконечной  памятью. 

Это значит, что, хотя в каждый момент объем хранящейся в ее памя-  ти информации конечен, для него нет никакой верхней грани. 

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

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

_21.2. Интуитивное понятие машины Тьюринга 

Машина Тьюринга - абстрактная вычислительная  машина,  которая  имеет:  ленту (память),  алфавит, управляющую головку, внутренние  состояния и программу. 

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