Рассмотрим функцию , которая возвращает 1, если n нулей последовательно появляются в π . Теперь кто-то дал мне доказательство того, что f ( n ) вычислимо:
Либо для всех n, появляется в π , либо am am 0 m появляется в π, а 0 m + 1 - нет. Для первой возможности f ( n ) : = 1 ; Для второго f ( n ) : = 1, если n ≤ m , иначе 0.
Автор утверждает, что это доказывает вычислимость , поскольку существует алгоритм для его вычисления.
Это доказательство правильно?
computability
Майк Б.
источник
источник
Ответы:
Подумайте об этом так, Майк: Это доказательство «разветвляется» на несколько возможных случаев, один из которых должен быть верным (используя закон исключенного среднего, который для каждого предложения либо p является истинным, либо ¬ p истинным). Но в конце каждой из этих веток вам всегда удается доказать, что функция f вычислима. Следовательно, независимо от того, какой из случаев действительно имеет место в реальной жизни, f должно быть вычислимо. (Однако точная причина, по которой f вычислима, будет отличаться в зависимости от ветви.)p p ¬p f f f
источник
Верно. Это то же самое, что и следующее: определите как постоянную функцию x ↦ 0, если Бог существует, и x ↦ 1f(x) x↦0 x↦1 если Бога не существует. Результирующая функция является постоянной функцией, поэтому вычислимой. То, что вы не можете сделать, это дать эту функцию, но сама функция вычислима.
Здесь одна из двух возможностей верна: либо существует такая , либо ее нет. Функция является либо постоянной функцией x ↦ 1, либо простой пороговой функцией, определенной с помощью m .m x↦1 m
источник
Я думаю - и надеюсь - что каждый студент информатики сталкивается с этой проблемой, которая кажется парадоксом. Это очень хороший пример различия вычислимых в смысле TCS и вычислимых в практическом смысле.
Тогда я думал: «Да, если бы я знал ответ, он был бы явно вычислим. Но как узнать?» Хитрость заключается в том, чтобы избавить себя от иллюзии, что вы должны выяснить, имеет ли это свойство или нет. Потому что это, очевидно (читай: imho), не может быть сделано машиной Тьюринга (до тех пор, пока у нас нет больше знаний, чем о π ).π π
Рассмотрим ваше определение вычислимости: мы говорим, что вычислимо (по Тьюрингу) тогда и только тогда, когда ∃ M ∈ T M : f M = f . То есть вам нужно только показать существование соответствующей машины Тьюринга, а не дать ее . То, что вы - мы - пытаемся сделать, - это вычислить машину Тьюринга, которая вычисляет требуемую функцию. Это намного сложнее!f ∃M∈TM:fM=f
Основная идея доказательства такова: я даю вам бесконечный класс функций, все они вычислимы (чтобы показать; здесь тривиально). Затем я докажу, что функция, которую вы ищете, находится в этом классе (чтобы показать; здесь различие в регистре). QED
источник
Да, верно, его вычислимо. Проблема в том, что ваша функция на самом деле не дает решения бесконечного семейства проблем, а способ (скажем) функции, вычисляющей решение проблемы остановки, - так что нет никаких проблем с вычислениями. Вместо этого вы представляете в форме функции какой-то один математический факт с конечным представлением - либо целое число, либо тот факт, что f является постоянно 1-й функцией
Можно кодировать Остановки проблемы в отдельных реальных числах, как постоянное Chaitan в , но целые числа всегда имеют конечные представления и поэтому могут быть закодированы как Тьюринг машины.Ω
Конечно, найти правильный алгоритм может быть сложной задачей. Но найти правильные алгоритмы обычно сложно!
источник
сообщение немного старое, но хотел опубликовать другой ответ.
Это неконструктивное доказательство (или аргумент) вычислимости. Это просто говорит о том, что функция должна существовать в некотором смысле, так как я могу представить ее (или, точнее, индексировать ее) в наборе (или вселенной) вычислимых функций. Однако он не создает ни саму машину (т.е. алгоритм), ни индекс (при условии эффективного перечисления вычислимых машин). Английская фраза « спасибо ни за что » кажется в этих случаях наиболее подходящей, например, следующая:
Люди в истории математики довольно много спорили о реальной действительности (или диапазоне действия) и значении таких аргументов. Конечный результат состоит в том, что аргументы такого же типа вновь появляются в теоремах Гёделя о неполноте и восстанавливают это «предположение о замкнутой вселенной» .
Если вам не нравятся эти аргументы, я бы не стал вас винить.
источник