304
правки
Изменения
первая версия, неформальное описание и неполное определение
{{В разработке}}
== Введение ==
'''Машина Тьюринга''' — абстрактный вычислитель, предложенный британским математиком Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Неформально машина Тьюринга определяется как устройство, состоящее из двух частей:
* бесконечной одномерной ленты, разделённой на ячейки,
* головкой, которая представляет из себя детерминированный конечный автомат. За один шаг головка может перезаписать символ под лентой и сместиться на одну ячейку
== Определение ==
Формально машина Тьюринга определяется как кортеж из восьми элементов <tex>\langle \Sigma, \Pi, B, Q, Y, N, S, \delta \rangle</tex>, где
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова
* <tex>\Pi \supseteq \Sigma</tex> — символы, которые могут быть записаны на ленту в процессе работы машины
* <tex>B \in \Pi \setminus \Sigma</tex> — пробельный символ (от слова ''blank'')
* <tex>Q</tex> — множество состояний управляющего автомата
* <tex>Y \in Q</tex> — допускающее состояние автомата
* <tex>N \in Q</tex> — отвергающее состояние автомата
* <tex>S \in Q</tex> — стартовое состояние автомата
* <tex>\delta : Q \times \Pi \to Q \times \Pi \times \{ \leftarrow, \rightarrow, \downarrow \}</tex> — функция перехода автомата
== Введение ==
'''Машина Тьюринга''' — абстрактный вычислитель, предложенный британским математиком Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Неформально машина Тьюринга определяется как устройство, состоящее из двух частей:
* бесконечной одномерной ленты, разделённой на ячейки,
* головкой, которая представляет из себя детерминированный конечный автомат. За один шаг головка может перезаписать символ под лентой и сместиться на одну ячейку
== Определение ==
Формально машина Тьюринга определяется как кортеж из восьми элементов <tex>\langle \Sigma, \Pi, B, Q, Y, N, S, \delta \rangle</tex>, где
* <tex>\Sigma</tex> — алфавит, из букв которого могут состоять входные слова
* <tex>\Pi \supseteq \Sigma</tex> — символы, которые могут быть записаны на ленту в процессе работы машины
* <tex>B \in \Pi \setminus \Sigma</tex> — пробельный символ (от слова ''blank'')
* <tex>Q</tex> — множество состояний управляющего автомата
* <tex>Y \in Q</tex> — допускающее состояние автомата
* <tex>N \in Q</tex> — отвергающее состояние автомата
* <tex>S \in Q</tex> — стартовое состояние автомата
* <tex>\delta : Q \times \Pi \to Q \times \Pi \times \{ \leftarrow, \rightarrow, \downarrow \}</tex> — функция перехода автомата
