У меня проблема:
Покажите, что существует действительное число, для которого не существует ни одной программы, которая работает бесконечно долго и записывает десятичные цифры этого числа.
Я полагаю, что это можно решить, сведя его к проблеме остановки, но я понятия не имею, как это сделать.
Буду также признателен за ссылки на подобные проблемы для дальнейшей практики.
algorithms
reductions
halting-problem
fresheed
источник
источник
Объясните в одно предложение, почему существует такое вещественное число, для которого не существует программы, которая будет работать бесконечно долго и выписывать цифры его представления в десятичной системе счисления. Надеюсь, кто-нибудь улучшит мой перевод.Ответы:
Как указывает Себастьян, существует только (бесконечно, но) много программ. Список их, чтобы создать список программ. Список (бесконечно, но) счетно длинный. Каждая программа генерирует одно число в R. Из этого мы можем создать (бесконечный, но) счетный список чисел в R. Теперь мы можем напрямую применить диагональный аргумент Кантора, чтобы доказать, что все еще должны быть другие числа.
Кстати, если алгоритм имеет (конечные) аргументы, вы можете просто переписать его как «более длинный» список программ, где у каждой программы нет аргументов.
Что касается вашего комментария «Что делать, если в качестве аргумента разрешены действительные числа», то предпосылка вопроса неверна: тогда все числа в R могут быть сгенерированы. Если кто-то находит число, скажем, 皮, и утверждает, что его нельзя вычислить, у нас есть следующий «алгоритм»:
и вызвать func (皮)
источник
Это на самом деле намного проще. Там только счетное количество алгоритмов. Тем не менее, существует бесчисленное множество реальных чисел. Так что, если вы попытаетесь соединить их, некоторые реальные цифры останутся без ответа.
источник
источник
Число представляет собой бесконечно длинное число, которое после десятичной точки кодирует так или иначе все машины Тьюринга, которые не останавливаются. С этим номером вы сможете решить проблему остановки.
Вы можете «искать» ТМ по номеру и запускать его параллельно. Если ТМ останавливается, он останавливается. Если нет, вы бы «нашли его код в номере».
Существует множество модификаций доказательства, и вы сможете их воспроизвести после самого первого урока сложности :-)
источник
Точка движется по траектории с помощью функции y = 2x. Когда абсцисса не вычислимое число, у точки нет возможности вычислить свой путь, но мы знаем, что она продолжается. Так что невычисляемые числа могут существовать вообще.
источник