Что такое вычислимость?

Джоэл Дэвид Хэмкинс, профессор логики, Оксфордский университет Эта лекция основана на главе 6 моей книги «Лекции по философии математики», опубликованной издательством MIT Press, https://mitpress.mit.edu/books/lectur.... Лекция 6. Вычислимость Что такое вычислимость? Курт Гёдель определил устойчивый класс вычислимых функций, примитивные рекурсивные функции, и всё же он дал основания для отчаяния в отношении полностью удовлетворительного ответа. Тем не менее, машинная концепция вычислимости Алана Тьюринга, выросшая из тщательного философского анализа природы человеческой вычислимости, оказалась устойчивой и заложила основу для современной компьютерной эры; широко признанный тезис Чёрча-Тьюринга утверждает, что Тьюринг был прав. Различие между вычислимой разрешимостью и вычислимой перечислимостью, подчеркнутое неразрешимостью проблемы остановки, показывает, что не все математические задачи могут быть решены машинным способом, и в теории бесконечной информации, в области степеней Тьюринга, нависает огромная иерархия. Теория сложности переориентирует предмет на область осуществимых вычислений, при этом все еще нерешенная проблема P против NP остается на заднем плане почти каждой серьезной проблемы в теоретической информатике.