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

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

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

Те́зис Чёрча — Тью́ринга — фундаментальное утверждение для многих областей науки, таких, как теория вычислимости, информатика, теоретическая кибернетика и др. Это утверждение было высказано Алонзо Чёрчем и Аланом Тьюрингом в середине 1930-х годов.

В самой общей форме оно гласит, что любая интуитивно вычислимая функция является частично вычислимой, или, что то же самое, может быть вычислена некоторой машиной Тьюринга.

Тезис Чёрча — Тьюринга невозможно строго доказать или опровергнуть, поскольку он устанавливает «равенство» между строго формализованным понятием частично вычислимой функции и неформальным понятием «интуитивно вычислимой функции».

Физический тезис Чёрча — Тьюринга гласит: Любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга.



Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Смотреть что такое "Тезис Чёрча — Тьюринга" в других словарях:

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

  • Тезис Чёрча-Тьюринга — …   Википедия

  • Тезис Чёрча—Тьюринга — …   Википедия

  • ЧЁРЧА ТЕЗИС — принцип, согласно к рому класс функций, вычислимых с помощью алгоритмов в широком интуитивном смысле, совпадает с классом частично рекурсивных функций. Ч. т. это естественнонаучный факт, подтверждаемый опытом, накопленным в математике за всю ее… …   Математическая энциклопедия

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

  • Алгоритм — У этого термина существуют и другие значения, см. Алгоритм (значения). Для улучшения этой статьи желательно?: Переработать оформление в соответствии с правил …   Википедия

  • Теория алгоритмов — Теория алгоритмов  наука, изучающая общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. К задачам теории алгоритмов относятся формальное доказательство алгоритмической неразрешимости задач,… …   Википедия

  • Тьюринг — Тьюринг, Алан Матисон Алан Тьюринг Alan Mathison Turing Памятник в Сэквиль Парке Дата рождения …   Википедия

  • Тьюринг, Алан Матисон — Алан Тьюринг Alan Turing Памятник в Сэквиль Парке Дата рождения: 23 июня 1912 Место рождения: Лондон, Англия Дата смерти: 7 июня 1954 …   Википедия

  • Тьюринг А. М. — Алан Тьюринг Alan Turing Памятник в Сэквиль Парке Дата рождения: 23 июня 1912 Место рождения: Лондон, Англия Дата смерти: 7 июня 1954 …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»