Когда Тьюринг впервые разработал так называемые машины Тьюринга, он делал это по чисто теоретическим причинам (они использовались для доказательства существования неразрешимых проблем) и фактически не создавал их в реальном мире.Перенесемся в настоящее время, и, за исключением любителей, создающих машины Тьюринга для удовольствия, ТМ по существу ограничиваются Теорией.
Машины Тьюринга на практике не используются по нескольким причинам.Для начала, невозможно создать настоящую ТМ, так как вам понадобятся бесконечные ресурсы для создания бесконечной ленты.(Вы могли бы представить себе создание ТМ с ограниченным количеством ленты, а затем добавление большего количества ленты по мере необходимости.) Более того, машины Тьюринга по своей природе медленнее, чем другие модели вычислений, из-за последовательного характера их доступа к данным.Например, машины Тьюринга не могут прыгнуть в середину массива, не пройдя сначала все элементы массива, которые он хочет пропустить.Кроме того, машины Тьюринга чрезвычайно сложны в разработке.Например, попробуйте написать машину Тьюринга для сортировки списка 32-битных целых чисел.(На самом деле, пожалуйста, не надо. Это действительно сложно!)
Тогда возникает вопрос ... зачем вообще изучать машины Тьюринга?К счастью, для этого есть огромное количество причин:
Чтобы определить пределы того, что можно вычислить.Поскольку машины Тьюринга способны моделировать любой компьютер на планете Земля (или, согласно тезису Черча-Тьюринга, любое физически реализуемое вычислительное устройство), если мы сможем показать пределы того, что машины Тьюринга могут вычислить, мы можем продемонстрировать пределы того, чтомог когда-либо надеяться, что это будет выполнено на реальном компьютере.
Формализовать определение алгоритма.Почему бинарный поиск является алгоритмом, а выражение «угадать ответ» - нет?Чтобы ответить на этот вопрос, у нас должна быть формальная модель того, что такое компьютер и что означает алгоритм.Наличие машины Тьюринга в качестве модели вычислений позволяет нам строго определить, что такое алгоритм.На самом деле никто никогда не хочет переводить алгоритмы в формат, но способность сделать это дает области алгоритмов и теории вычислим твердое математическое обоснование.
Формализовать определения детерминированных и недетерминированныхалгоритмы.Вероятно, самый большой открытый вопрос в области компьютерных наук сейчас - P = NP .Этот вопрос имеет смысл, только если у вас есть формальное определение для P и NP, а они, в свою очередь, требуют определений для детерминированных и недетерминированных вычислений (хотя технически они могут быть определены с использованием логики второго порядка).Наличие машины Тьюринга позволяет нам говорить о важных проблемах в NP, а также дает нам возможность находить NP-полные проблемы.Например, доказательство того, что SAT является NP-полным, использует тот факт, что SAT можно использовать для кодирования машины Тьюринга и ее выполнения на входе.
Надеюсь, это поможет!