Компьютерная Лаборатория

1. Что такое машина Тьюринга? Машина Тьюринга - это гипотетическая машина, о которой математик Алан...
2. Простая программа
3. Состояние машины
4. Конечные автоматы

Что такое машина Тьюринга?

Машина Тьюринга - это гипотетическая машина, о которой математик Алан Тьюринг придумал в 1936 году. Несмотря на свою простоту, машина может имитировать ЛЮБОЙ компьютерный алгоритм, каким бы сложным он ни был!

Выше очень простое представление машины Тьюринга. Он состоит из бесконечно длинной ленты, которая действует как память в типичном компьютере или в любой другой форме хранения данных. Квадраты на ленте обычно пустые в начале и могут быть написаны с символами. В этом случае машина может обрабатывать только символы 0 и 1 и «» (пусто) и, таким образом, называется машиной Тьюринга с 3 символами.

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

1. Прочитайте символ на квадрате под головой.
2. Отредактируйте символ, написав новый символ или удалив его.
3. Переместите ленту слева направо на один квадрат, чтобы машина могла читать и редактировать символ на соседнем квадрате.

Простая демонстрация

В качестве тривиального примера, демонстрирующего эти операции, давайте попробуем напечатать символы «1 1 0» на изначально чистой ленте:

Сначала мы пишем 1 на квадрате под головой:

Далее мы перемещаем ленту влево на одну клетку:

Теперь напишите 1 на новом квадрате под заголовком:

Затем мы снова перемещаем ленту влево на одну клетку:

Наконец, напишите 0 и все!

Простая программа

С символами «1 1 0», напечатанными на ленте, давайте попробуем преобразовать 1 в 0 и наоборот. Это называется инверсией битов, поскольку 1 и 0 - это двоичные биты. Это можно сделать, передав следующие инструкции машине Тьюринга, используя возможности чтения машины, чтобы самостоятельно решать ее последующие операции. Эти инструкции составляют простую программу.

Символ чтения Инструкция записи Инструкция перемещения Пусто Нет Нет 0 Запись 1 Переместить ленту вправо 1 Запись 0 Переместить ленту вправо

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

Давайте посмотрим, что эта программа делает с нашей лентой из предыдущего конечного пункта инструкций:

Текущий символ под заголовком - 0, поэтому мы пишем 1 и перемещаем ленту вправо на один квадрат.

Читаемый символ теперь равен 1, поэтому мы пишем 0 и перемещаем ленту вправо на один квадрат:

Аналогично, символ чтения равен 1, поэтому мы повторяем одни и те же инструкции.

Наконец, «пустой» символ читается, поэтому машина ничего не делает, кроме непрерывного чтения пустого символа, поскольку мы дали ему команду повторить последовательность чтения-записи-перемещения без остановки.

На самом деле программа неполная. Как машина повторяет последовательность бесконечно, и как машина прекращает запуск программы? Программа рассказывает это с концепцией состояния машины .

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

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

Состояние

Символ чтения Инструкция записи Инструкция перемещения Следующее состояние Состояние 0 Пусто Нет Нет Состояние останова 0 Запись 1 Перемещение ленты в правильное состояние 0 1 Запись 0 Перемещение ленты в правильное состояние 0

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

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

Конечные автоматы

Хотя это кажется глупым, давайте теперь добавим в нашу программу дополнительное состояние, которое возвращает уже инвертированные биты «1 1 0» обратно с «0 0 1» в «1 1 0». Ниже обновленная таблица с изменениями, выделенными курсивом . Теперь машина Тьюринга работает как конечный автомат с двумя состояниями - они называются трехсимвольными машинами Тьюринга с двумя состояниями.

Состояние Символ чтения Инструкция записи Инструкция перемещения Следующее состояние Состояние 0 Пусто Запись пусто Переместите ленту влево Состояние 1 0 Запись 1 Переместите ленту вправо Состояние 1 1 Запись 0 Переместите ленту вправо Состояние 0 Состояние 1 Пусто Написать пусто Переместить лента вправо Стоп-состояние 0 Запись 1 Перемещение ленты в левое состояние 1 1 Запись 0 Перемещение ленты в левое состояние 1

Для инструкции записи «None» было изменено на «Write blank» для единообразия (так что упоминаются только символы машины), и следует отметить, что они эквивалентны.

Вместо таблицы состояний программа также может быть представлена ​​диаграммой состояний:

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

Затем мы снова инвертируем биты, на этот раз перемещая ленту влево, а не вправо.

Наконец, читается пустой символ, поэтому мы перемещаем ленту вправо, чтобы вернуться к тому, с чего начали, и останавливаем программу.

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

В второй раздел Давайте узнаем о светодиодах, выводах GPIO, резисторах и питоне, прежде чем приступить к созданию нашей машины Тьюринга!

Похожие

Комментарии