Тезис Чёрча — Тьюринга
| Русская Википедия - свободная энциклопедия | Скачать словарь |
Тезис Чёрча — Тьюринга
Те́зис Чёрча — Тью́ринга — фундаментальное утверждение для многих областей науки, таких, как теория вычислимости, информатика, теоретическая кибернетика и др. Это утверждение было высказано Алонзо Чёрчем и Аланом Тьюрингом в середине 1930-х годов.
В самой общей форме оно гласит, что любая интуитивно вычислимая функция является частично вычислимой, или, что тоже самое, может быть вычислена некоторой машиной Тьюринга.
Тезис Чёрча — Тьюринга невозможно строго доказать или опровергнуть, поскольку он устанавливает «равенство» между строго формализованным понятием частично вычислимой функции и неформальным понятием «интуитивно вычислимой функции».
| Продолжение на Wikipedia.οrg... |
© Текстовое содержимое использует материал из Википедии® и доступно в соответствии с лицензией свободной документации GNU
