Машина Тьюринга - реальное устройство или воображаемая концепция?

Когда я изучал машины Тьюринга и КПК, я думал, что первым вычислительным устройством была машина Тьюринга.

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

Поэтому я спросил, как входные строки представлены в магнитных лентах, но по ответу и деталям, приведенным в моей книге, я узнал, что машина Тьюринга несколько гипотетична.

Мой вопрос: как машина Тьюринга будет реализована на практике? Например, как это используется для проверки орфографических ошибок в наших текущих процессорах.

Машины Тьюринга устарели? Или они все еще используются?

Ответ 1

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

Машины Тьюринга не используются на практике по нескольким причинам. Для начала, невозможно создать настоящую ТМ, так как вам понадобятся бесконечные ресурсы для создания бесконечной ленты. (Вы могли бы представить себе создание ТМ с ограниченным количеством ленты, а затем добавление большего количества ленты по мере необходимости.) Более того, машины Тьюринга по своей природе медленнее, чем другие модели вычислений, из-за последовательного характера их доступа к данным. Например, машины Тьюринга не могут прыгнуть в середину массива, не пройдя сначала все элементы массива, которые он хочет пропустить. Кроме того, машины Тьюринга чрезвычайно сложны в разработке. Например, попробуйте написать машину Тьюринга для сортировки списка 32-битных целых чисел. (На самом деле, пожалуйста, не надо. Это действительно сложно!)

Тогда возникает вопрос... зачем вообще изучать машины Тьюринга? К счастью, для этого есть огромное количество причин:

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

Надеюсь это поможет!

Ответ 2

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

Здесь видео одного: http://www.youtube.com/watch?v=E3keLeMwfHY

Ответ 3

Это теоретическая машина, следующий абзац из Википедии

Машина Тьюринга - это теоретическое устройство, которое манипулирует символами на ленте в соответствии с таблицей правил. Несмотря на свою простоту, машина Тьюринга может быть адаптирована для имитации логики любого компьютерного алгоритма и особенно полезна для объяснения функций процессора внутри компьютера.

Эта машина вместе с другими машинами, такими как недетерминированная машина (не существует в реальности), очень полезна для вычисления сложности и доказывает, что один алгоритм сложнее другого или один алгоритм не решаем... и т.д.

Ответ 4

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

Ответ 5

Машина Тьюринга (ТМ) представляет собой математическую модель для вычислительных устройств. Это самая маленькая модель, которая действительно может вычислить. На самом деле компьютер, который вы используете, - очень большая ТМ. ТМ не устарела. У нас есть другие модели для вычислений, но эта использовалась для создания современных компьютеров, и поэтому мы многим обязаны Алану Тьюрингу, который предложил эту модель в 1936 году.