В информатике и квантовой физике принцип Чёрча–Тьюринга–Дойча ( принцип CTD ) является более сильной физической формой тезиса Чёрча–Тьюринга, сформулированного Дэвидом Дойчем в 1985 году. [1] Принцип гласит, что универсальное вычислительное устройство может моделировать любой физический процесс .
Этот принцип был сформулирован Дойчем в 1985 году в отношении конечных машин и процессов. Он заметил, что классическая физика , которая использует концепцию действительных чисел , не может быть смоделирована машиной Тьюринга , которая может представлять только вычислимые действительные числа . Дойч предположил, что квантовые компьютеры могут фактически подчиняться принципу CTD, предполагая, что законы квантовой физики могут полностью описать каждый физический процесс.
Более ранняя версия этого тезиса для классических компьютеров была сформулирована другом и учеником Алана Тьюринга Робином Ганди в 1980 году. [2] [3]
Похожий тезис был выдвинут Майклом Фридманом в раннем обзоре топологических квантовых вычислений с Алексеем Китаевым , Майклом Дж. Ларсеном и Чжэнханом Вангом , известном как тезис Фридмана-Черча-Тьюринга: [4]
«Все «разумные» вычислительные модели, которые добавляют ресурсы квантовой механики (или квантовой теории поля) к классическим вычислениям, приводят (эффективно) к интерсимулируемым классам: существует одна квантовая теория вычислений».
Этот тезис отличается от тезиса Чёрча-Тьюринга-Дойча тем, что он представляет собой утверждение о вычислительной сложности, а не о вычислимости.