Вместо этого используйте машины Тьюринга…

Название немного вводит в заблуждение. Это должно быть: «Не используйте детерминированные конечные автоматы (DFA). Вместо этого используйте машины Тьюринга».

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

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

  • DFA имеет только состояния и переходы. Его память ограничена только знанием того, в каком состоянии он находится. Учитывая новый ввод или событие, исходя из его текущего состояния, он может перейти в новое состояние (или остаться в текущем состоянии). Он не может вернуться назад и прочитать более ранние входные данные или события. Он просто продолжает потреблять входные данные, пока их не останется.
  • У машины Тьюринга есть память; он может вернуться и прочитать любые предыдущие входные данные (или приостановить чтение), а также изменить входные данные и свою память. Он использует как входные данные, так и память, чтобы решить, каким будет его следующее состояние (может быть одним и тем же состоянием).

Good Read: Понимание конечных автоматов.

Так в чем же дело?

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

DFA отлично подходят для задач, которым требуется мало памяти. Турникет — классический пример. Он закрыт для входа, пока вы не вставите монету. Затем он открывается, чтобы впустить одного человека, после чего снова закрывается. Промыть и повторить.

Турникету не нужна память, кроме текущего состояния. Ему не нужно возвращаться и читать более ранние входные данные. Итак, да, ДФА.

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

Если мы используем DFA, нам нужно будет предоставить память и много связующего кода. Реализация разбивается повсюду.

Кошмар.

Другой способ взглянуть на эти два:

  • Токарные станки могут делать что угодно с DFA, а не наоборот.
  • Любая компьютерная программа является машиной Тьюринга.

Поэтому, если вы думаете о своей следующей реализации и видите дискретные состояния и думаете: «Конечный автомат!», сделайте паузу и подумайте, нужен ли вам DFA или машина Тьюринга.

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