Зачем изучать множество моделей, если они вычисляют одни и те же функции?

Эквивалентность справедлива только для того, что может быть вычислено в принципе. Различные модели облегчают выражение или анализ разных вещей: лямбда-исчисление проясняет функциональное программирование, схемы показывают параллелизм и аппаратные затраты, а квантовые модели отражают физические явления, поэтому каждая из них является подходящей линзой для разных вопросов.

Все ли модели вычислений эквивалентны?

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

Модели вычислений

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

Найти тему в PaperMindСкороFind papers & topics

Tools & resources

Скачать слайды

Learn & explore

ВидеоСкоро

Definition

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

Scope

Эта область охватывает лямбда-исчисление и функциональные модели, рекурсивные функции и регистровые машины, булевы схемы и сложность схем, а также квантовые вычисления, исследуя, как каждая модель выражает алгоритмы, как их вычислительная мощность связана через тезис Чёрча–Тьюринга и как их эффективность может расходиться.

Sub-topics

Core questions

Какие существуют различные способы формализации понятия вычисления?
Какие модели эквивалентны по функциям, которые они могут вычислять, и почему?
Чем отличаются модели, когда важны эффективность, параллелизм или физическая реализуемость?
Может ли физически обоснованная модель, такая как квантовые вычисления, превзойти классическую эффективность?

Key theories

Эквивалентность согласно тезису Чёрча–Тьюринга: Лямбда-исчисление, рекурсивные функции, регистровые машины и машины Тьюринга вычисляют один и тот же класс функций, что является основой для отождествления вычислений с тьюринговой вычислимостью.
Различия в эффективности: Модели, которые согласуются в вычислимости, могут резко различаться по ресурсам: схемы демонстрируют параллельные и неоднородные вычисления, а квантовые модели, по-видимому, предлагают ускорения, поэтому выбор модели имеет большое значение для сложности, даже если он не имеет значения для вычислимости.

Clinical relevance

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

History

В 1930-х годах лямбда-исчисление Чёрча, рекурсивные функции Гёделя и Клини, а также машины Тьюринга были предложены по отдельности, а затем показана их эквивалентность. Более поздние модели добавили новые измерения: сложность схем формализовала параллельные и аппаратные вычисления, а предложение Фейнмана 1982 года о квантовом моделировании положило начало квантовой модели вычислений.

Key figures

Alonzo Church
Alan Turing
Stephen Kleene
Richard Feynman

Seminal works

church1936
sipser2013
aroraBarak2009

Frequently asked questions

Зачем изучать множество моделей, если они вычисляют одни и те же функции?: Эквивалентность справедлива только для того, что может быть вычислено в принципе. Различные модели облегчают выражение или анализ разных вещей: лямбда-исчисление проясняет функциональное программирование, схемы показывают параллелизм и аппаратные затраты, а квантовые модели отражают физические явления, поэтому каждая из них является подходящей линзой для разных вопросов.
Все ли модели вычислений эквивалентны?: Все разумные классические модели вычисляют один и тот же класс функций, что подтверждает тезис Чёрча–Тьюринга. Но они могут сильно различаться по эффективности, и модели, использующие различные ресурсы, такие как квантовая суперпозиция, могут решать определенные задачи быстрее, даже вычисляя те же функции.