Тезис Чёрча — Тьюринга — Дойча

Тезис Чёрча — Тьюринга — Дойча (CTD-принцип — по аббревиатуре от Church, Turing, Deutsch; также сильный тезис Чёрча — Тьюринга) — более строгая в физическом смысле формулировка эвристического вычислительного тезиса Чёрча — Тьюринга, предложенная Дэвидом Дойчем в 1985 году.

Согласно тезису, универсальное компьютерное устройство способно моделировать любой конечный физический процесс; при этом аппарат классической физики, существенным образом использующий понятия непрерывности и континуума, не позволяет моделировать все физические процессы машиной Тьюринга, которая оперирует лишь с вычислимыми объектами. Дойч предположил, что квантовые компьютеры смогут превозмочь ограничения данного принципа, если алгебраические законы квантовой физики смогут стать теоретической базой, описывающей любые физические процессы, и описал квантовую машину Тьюринга — достаточно простую абстрактную машину, моделирующую квантовые алгоритмы, и сформулировал расширенный вариант тезиса Чёрча — Тьюринга.

Вопрос о внутреннем содержании тезиса и возможности сверхтьюринговых вычислений — предмет исследований цифровой физики.

СсылкиПравить

• Deutsch, D. Quantum theory, the Church–Turing principle and the universal quantum computer (англ.) // Proceedings of the Royal Society : journal. — London, 1985. — No. 400. — P. 97—117. (недоступная ссылка)
• Deutsch, D. 6: Universality and the Limits of Computation // The Fabric of Reality  (англ.) (рус. (Структура реальности) (рус.). — New York: Allan Lane, 1997. — ISBN 014027541X.