Всем привет! С вами канал Умная Планета! Перед тем как мы начнем, хотим попросить вас подписаться на наш канал и поставить лайк - это очень мотивирует! Всем приятного прочтения!
Наверное, почти каждый человек который читает эту статью ни разу не слышал, или слышал, но все равно не знает что такое Машина Тьюринга. Пришло время это исправить!
Машина Тьюринга — абстрактный исполнитель (или, если говорить простым языком это абстрактная вычислительная машина). Она была предложена английским математиком Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать всех исполнителей, каким-либо образом реализующих процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен и прост.
То есть всякий интуитивный (простой) алгоритм может быть реализован с помощью некоторой машины Тьюринга.
Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj→qi1aj1dk (если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации <qi, aj> имеется ровно одно правило (для недетерминированной машины Тьюринга может быть большее количество правил). Правил нет только для заключительного состояния, попав в которое, машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.
Интересные ссылки:
Топ 10 САМЫХ дорогих домов в мире.
Топ 10 великих футболистов мира.
На сегодня это все! Подписывайтесь на наш канал, ставьте лайки и пишите свой комментарий. Всем пока!