Машина Тьюринга - это интересно. Часть 3

Теперь перейдем к самому интересному вопросу: для чего же нужны машины Тьюринга? Как и где их использовать?

Главное, что умеют машины Тьюринга - это осуществлять любые вычисления, какими сложными они бы ни были (есть некоторые суперспецифические исключения из этого правила, но о них пока не будем). С виду машина Тьюринга - это очень простой механизм (см Часть 1 и Часть 2): бесконечная лента из нулей и единиц, вдоль которой движется считывающая головка, меняющая символы на ленте и свои внутренние состояния в соответствии с заложенной в нее программой (изображение взято с сайта https://commons.wikimedia.org/) Но этот простенький механизм может почти все: можно сделать машину Тьюринга, которая будет возводить любое число в квадрат или в любую другую степень; можно сделать машину Тьюринга, которая будет складывать друг с другом или умножать друг на друга любое количество чисел, вычитать их друг из друга и т.д. Изощренные машины Тьюринга могут даже работать с дробями и иррациональными числами.

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

И ЭТА ЕГО МОДЕЛЬ - МАШИНА ТЬЮРИНГА - ЛЕЖИТ В ОСНОВЕ ВСЕХ СОВРЕМЕННЫХ КОМПЬЮТЕРОВ. Взгляните на жесткий диск (винчестер) - это не что иное как считывающая головка, которая движется вдоль "ленты" (пластины, разбитой на миллиарды "клеточек")  и записывает на нее биты информации (изображение взято с сайта http://www.freepik.com/)

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

Ну, а теперь приведу пример машины Тьюринга, которая добавляет к каждому числу единицу. Это машина, у которой есть всего одного состояние (№ 1) и два правила перехода (см. Часть 2, в которой рассказывается про состояния машины Тьюринга и правила перехода):

Правило 1. "Если машина находится в состоянии №1, а считывающая головка стоит напротив единицы, то оставь единицу, останься в состоянии № 1 и сдвинься на одну клеточку влево".

Правило 2. "Если машина находится в состоянии №1, а считывающая головка стоит напротив нуля, то нарисуй вместо нуля единицу и заверши работу".

Посмотрим по шагам, как работает эта машина. Если ей подано на вход какое-нибудь число, например, 5, то это означает, что на ленте нарисованы 5 единиц и в начале своей работы машина стоит возле самой левой единицы в состоянии №1. Что она сделает? 

Первый шаг. В соответствии с Правилом 1, машина оставит эту единицу нетронутой, останется в состоянии № 1 и сдвинет считывающую головку на одну клетку влево.

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

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

Еще один пример: машина Тьюринга, которая всегда выдает на выходе 0, в независимости от того, какое число подано ей на вход. У нее тоже одно состояние (№ 1) и два правила перехода.

Правило 1. "Если машина находится в состоянии №1, а считывающая головка стоит напротив единицы, то нарисуй вместо единицы 0 , останься в состоянии №1 и сдвинься на одну клеточку вправо".

Правило 2. "Если машина находится в состоянии №1, а считывающая головка стоит напротив нуля, то оставь нуль и заверши работу".

Посмотрим по шагам, как работает эта машина. Можно опять на примере числа 5 - на ленте нарисованы 5 единиц и в начале своей работы машина стоит возле самой левой единицы в состоянии №1. 

Первый шаг. В соответствии с Правилом 1, машина нарисует вместо единицы ноль, останется в состоянии № 1 и сдвинет считывающую головку на одну клетку вправо.

Второй шаг. На ленте осталось четыре единицы, а считывающая головка опять стоит напротив самой левой из них в состоянии № 1. Поэтому в соответствии с Правилом 1, она нарисует вместо нее ноль, останется в состоянии № 1 и сдвинет считывающую головку еще на одну клетку вправо.

Третий шаг. На ленте осталось три единицы, машина опять сотрет одну из них и сдвинется вправо.

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

Пятый шаг. На ленте осталась последняя единица, машина сотрет ее.

Шестой шаг. На ленте не осталось единиц, машина будет действовать в соответствии с Правилом 2 и завершит свою работу. На выходе она выдаст 0, потому что на ленте нет ни одной единицы.

Вот так работает машина Тьюринга (а значит и все современные компьютеры).