Квантово-вычислительные машины и машины Тьюринга. Являются ли машины Тьюринга точной мерой?

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

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

Она сказала, что в отношении дискурса классов время выполнения конкретного алгоритма на машине Тьюринга не меняет определения вычислимости или мощности, с которой мы измеряем вычислимость. «Мы обеспокоены тем, что вычислимо, а не тем, что эффективно вычислимо на данном этапе». Таким образом, не имеет значения, если на машинах Тьюринга появляется все больше и больше лент, а все больше и больше лент подразумевают, что они могут вычисляться за меньшие шаги. Хорошо, я понимаю, что мы действительно фокусируемся на том, что можно вычислить, а не на скорости, с которой мы можем это вычислить.

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

Итак, у меня есть пара вопросов:

1. Предположим, у нас есть модель для квантовой машины Тьюринга , она должна быть эквивалентна «обычной» машине Тьюринга, верно?

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

2. Это что-то над моей головой, и я должен удалить этот пост? Я не хочу быть преждевременным, я просто не видел вопрос, похожий на мой.

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

Теория сложности зародилась как попытка решения этой проблемы. Теория сложности изучает, насколько сложно, с точки зрения времени и пространства, вычислить определенные предикаты и функции. С точки зрения теории сложности, не все вычислительные модели одинаковы, и машины Тьюринга взяты в качестве эталонной модели. Однако даже теория сложности не очень реалистична, поскольку она рассматривает все вычислительные модели, полиномиально эквивалентные машинам Тьюринга, одинаково (две модели являются полиномиально эквивалентными, если любая задача, разрешимая во времени и пространстве в одной модели может быть решена за время и пространство в другом, где - размер ввода иS ( n ) T ( n ) c S ( n ) c n c O ( 1 ) O ( n log n ) Ω ( n 2$T(n)$$S(n)$$T(n)^c$$S(n)^c$$n$$c$ - некоторая положительная постоянная). Например, машины Тьюринга не являются хорошими моделями для реальных компьютеров, поскольку они не поддерживают произвольный доступ (доступ к произвольной точке в памяти за время ). Конечно, произвольный доступ может моделироваться машиной Тьюринга, но моделирование может быть медленным. Часто говорят, что сортировка может быть выполнена за время , но это не относится к машинам Тьюринга, которые, вероятно, требуют или перемещаются даже для сортировки целых чисел. Поэтому в области алгоритмов другие модели, такие как машина ОЗУ, заменяют машины Тьюринга.$O(1)$$O(n\log n)$$\Omega(n^2)$

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