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

Машина Тьюринга. Бесконечная лента. Головка, которая может перемещаться, записывать и считывать. Окей. Для чего это всё и что это вообще всё значит?
  • Вопрос задан
  • 8592 просмотра
Пригласить эксперта
Ответы на вопрос 7
Mrrl
@Mrrl
Заводчик кардиганов
В первую очередь - это формальное определение алгоритма. Задача считается алгоритмически разрешимой тогда и только тогда, когда её решение можно запрограммировать на машине Тьюринга (или каким-нибудь другим эквивалентным способом). Это определение даёт, например, возможность предъявить алгоритмически неразрешимые задачи. Позволяет ввести понятие "Тьюринг-полного" языка - если на языке можно реализовать машину Тьюринга, то на нём можно написать любой алгоритм (язык С таким не является, а C# - является).
В общем, МТ - способ определить некоторый класс алгоритмов:
- некоторые задачи можно решить конечным автоматом;
- для некоторых потребуется конечный автомат со стековой памятью;
- для других достаточно машины Тьюринга;
- для остальных требуется божественное откровение или другие неалгоритмизируемые методы.
Ответ написан
Moskus
@Moskus
Машина Тьюринга - простейшее устройство, которое реализует действия по алгоритму, учитывающему текущее состояние устройства и состояние текущей ячейки памяти (традиционно говорят о "ленте"). В случае так называемой детерминированной (то есть определенной) машины Тьюринга, каждой паре состояний устройства и текущей ячейки соответствует единственное элементарное действие (которое может включать перемещение по памяти и изменение состояния ячеек).
Эта теория используется для изучения принципов построения формальных алгоритмов на простейшем абстрактном примере.
Ответ написан
Комментировать
gbg
@gbg Куратор тега Программирование
Любые ответы на любые вопросы
Что любой компьютер представляет собой жутко переусложненную машину Тьюринга, правда с конечной лентой.

Изучать фундаментальную теорию алгоритмов проще на таком вот, вычурно элементарном компьютере, который гарантированно реализуем.
Ответ написан
Комментировать
EvilsInterrupt
@EvilsInterrupt
System programming, Reversing Engineering, C++
Странно что Вы вообще к компьютеру не докапываетесь. Ведь по сути любое вычислительное устройство это 2 инструкции. Одна из них NOT , а другая либо AND либо OR. Вот на этих двух NAND или NOR строится ВСЕ вычислительные устройства!
Ответ написан
Ну фильм же недавно вышел Игра в имитацию - весь фильм об этой машине. Посмотрите и всё поймёте. А к программированию, на мой взгляд тут уместно только одно слово - алгоритмы!
Ответ написан
kykyryky
@kykyryky
МТ дает представление о том, что такое алгоритм.
Ответ написан
Комментировать
uvelichitel
@uvelichitel
habrahabr.ru/users/uvelichitel
Этим взламывалась enigma во Вторую Мировую. На этом основана архитектура фон Неймана на которой был построен ENIAC и все компьютеры после. Это расширение конечного автомата, которым прошит любой контроллер, которое реализовано в любом парсере, лексере и компиляторе.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы