Принцип Чёрча – Тьюринга – Дойча

В информатике и квантовой физике принцип Чёрча-Тьюринга-Дойча ( принцип CTD ) является более сильной физической формой тезиса Чёрча-Тьюринга, сформулированного Дэвидом Дойчем в 1985 году. ^{[ 1 ]} Принцип гласит, что универсальное вычислительное устройство может моделировать любой физический процесс .

История

Этот принцип был сформулирован Дойчем в 1985 году в отношении финитных машин и процессов. Он заметил, что классическая физика , использующая концепцию действительных чисел , не может быть смоделирована машиной Тьюринга , которая может представлять только вычислимые действительные числа . Дойч предположил, что квантовые компьютеры действительно могут подчиняться принципу CTD, предполагая, что законы квантовой физики могут полностью описать каждый физический процесс.

Более ранняя версия этого тезиса для классических компьютеров была сформулирована другом и учеником Алана Тьюринга Робином Ганди в 1980 году. ^{[ 2 ]}^{[ 3 ]}

Похожий тезис был высказан Майклом Фридманом в раннем обзоре топологических квантовых вычислений совместно с Алексеем Китаевым , Майклом Дж. Ларсеном и Чжэнханом Вангом , известный как тезис Фридмана-Черча-Тьюринга. ^{[ 4 ]}:

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

Этот тезис отличается от тезиса Чёрча-Тьюринга-Дойча, поскольку он является утверждением о вычислительной сложности, а не о вычислимости.

См. также

Примечания

^ Нильсен, Майкл (16 апреля 2004 г.). «Интересные проблемы: Принцип Чёрча – Тьюринга – Дойча» . Проверено 10 мая 2014 г.
^ Ганди, Р. (1980). Тезис Чёрча и принципы механизмов. Исследования по логике и основам математики (101), 123–148.
^ Казначеев, Артем (2014). «Фальсифицируемость и вариант Ганди тезиса Чёрча-Тьюринга» . Блог группы «Теория, эволюция и игры» . Проверено 23 июля 2018 г.
^ Фридман, Майкл Х.; Китаев, Алексей; Ларсен, Майкл Дж.; Ван, Чжэнхань (20 сентября 2002 г.). «Топологические квантовые вычисления». arXiv : Quant-ph/0101025 .

Ссылки

Дойч, Д. (1985). «Квантовая теория, принцип Чёрча – Тьюринга и универсальный квантовый компьютер» (PDF) . Труды Королевского общества . 400 (1818): 97–117. Бибкод : 1985РСПСА.400...97Д . CiteSeerX 10.1.1.41.2382 . дои : 10.1098/rspa.1985.0070 . S2CID 1438116 . Архивировано из оригинала (PDF) 9 марта 2016 г. Проверено 17 августа 2011 г.

Дальнейшее чтение

Дойч, Д. (1997). «6: Универсальность и пределы вычислений». Ткань реальности . Нью-Йорк: Аллан Лейн. ISBN 978-0-14-027541-4 .
Кристофер Г. Тимпсон «Квантовые компьютеры: гипотеза Чёрча-Тьюринга против принципа Тьюринга» в книге Кристофа Тойшера, Дугласа Хофштадтера (ред.) Алан Тьюринг: жизнь и наследие великого мыслителя , Springer, 2004, ISBN 3-540-20020-7 , стр. 213–240.

Внешние ссылки

Нильсен, Майкл (16 апреля 2004 г.). «Интересные проблемы: Принцип Чёрча – Тьюринга – Дойча» .

[1] Нильсен, Майкл (16 апреля 2004 г.). «Интересные проблемы: Принцип Чёрча – Тьюринга – Дойча» . Проверено 10 мая 2014 г.

[2] Ганди, Р. (1980). Тезис Чёрча и принципы механизмов. Исследования по логике и основам математики (101), 123–148.

[3] Казначеев, Артем (2014). «Фальсифицируемость и вариант Ганди тезиса Чёрча-Тьюринга» . Блог группы «Теория, эволюция и игры» . Проверено 23 июля 2018 г.

[4] Фридман, Майкл Х.; Китаев, Алексей; Ларсен, Майкл Дж.; Ван, Чжэнхань (20 сентября 2002 г.). «Топологические квантовые вычисления». arXiv : Quant-ph/0101025 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]