Несколько недель назад я наткнулся на этот замечательный пост от JDH, и с тех пор он меня беспокоит. TL;DR для доказательства заключается в том, что мы можем закодировать выходные данные любой функции в аксиомы теории множеств, так что нам просто нужна одна машина Тьюринга, способная действовать как умный «анализатор», который может извлекать информацию из аксиом. и вычислить нужную функцию - это я понимаю (по крайней мере, концептуально и несколько формально).
Что меня смущает, так это философские последствия, которые это имеет для концепций вычислимости... Я полагал, что в некотором смысле существовало универсальное понятие вычислимости (т.е. были проблемы, которые либо разрешимы, либо не разрешимы), но это предполагает , что такие понятия зависят от теоретико-множественного фона для ваших вычислений - например, в этом посте Скотта Ааронсона обсуждается работа одного из его студентов по демонстрации того, что существует конкретная машина Тьюринга, поведение которой не зависит от ZFC (опять же, неявно предполагая, что что поведение является платоническим, но мы просто не можем доказать это в любом случае).
Простите меня за отсутствие четкости в моем вопросе, но: есть ли способ, которым это можно решить? Почему существуют кажущиеся невычислимыми задачи (чье доказательство невычислимости часто использует доказательство от противного, казалось бы, без ссылки на какой-либо теоретико-множественный фон, например проблема остановки), которые можно вычислить с помощью машины Тьюринга без использования (официально) оракула ? Оказывает ли это какое-либо влияние на тезис Черча-Тьюринга, поскольку, по-видимому, ни один человек не может надежно вычислить функцию занятого бобра, в то время как универсальный алгоритм (если его поместить в правильную вселенную) может?
Возможно, вы неправильно поняли один из ключевых аспектов этого поста Хэмкинса. Его теорема не говорит, что каждая функция вычислима (несмотря на название).
Вместо этого он говорит, что для любой заданной функции вы можете вычислить ее в какой-то тщательно выбранной вселенной, то есть в какой-то тщательно выбранной модели теории множеств. Вселенная, в которой вы можете его вычислить, будет различаться в зависимости от функции. Существует много, много, много разных моделей теории множеств, т. е. много разных теоретико-множественных вселенных (точно так же, как существует много, много, много разных моделей теории групп, т. е. много разных групп). Функция, которую вам дали, может быть вычислимой в одних моделях и невычислимой в других. Все, что гарантирует теорема, — это существование некоторой модели, в которой данная функция вычислима.
Джеймс Аратун
хмахольм ушел за Монику
Ли Мошер
Иски Мэтьюз
хмахольм ушел за Монику