Jump to content

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

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

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

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

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

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

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

См. также

[ редактировать ]

Примечания

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

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

[ редактировать ]
  • Дойч, Д. (1997). «6: Универсальность и пределы вычислений». Ткань реальности . Нью-Йорк: Аллан Лейн. ISBN  978-0-14-027541-4 .
  • Кристофер Г. Тимпсон «Квантовые компьютеры: гипотеза Чёрча-Тьюринга против принципа Тьюринга» в книге Кристофа Тойшера, Дугласа Хофштадтера (ред.) Алан Тьюринг: жизнь и наследие великого мыслителя , Springer, 2004, ISBN   3-540-20020-7 , стр. 213–240.
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 5dc045cc7d79c4a94e2cf24db5b18e3b__1721198760
URL1:https://arc.ask3.ru/arc/aa/5d/3b/5dc045cc7d79c4a94e2cf24db5b18e3b.html
Заголовок, (Title) документа по адресу, URL1:
Church–Turing–Deutsch principle - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)