Мне потребуется немного времени, чтобы дать вам развёрнутый ответ. Добавлю его в эту ветку комментариев. Пока лишь скажу - перед тем как обвинять кого-то в незнании основ, пожалуйста, убедитесь на 100%, что сами не ошиблись.
Остальное городить к тому, что вы ошиблись. Это сказано и в статье, и в комментариях. Данную ошибку уже совершили несколько людей. Ваш вариант считает некоторые слова по несколько раз, в частности слова, которые содержат fuck 2 и более раз. Так что могу лишь попросить быть внимательнее
Как раз таки нет, Rsa97 не прав. В приблизительном решении слово "fuckfuckfuckfuckfuck" (5 раз, ровно 20 букв) будет учтено 5 раз вместо одного, именно по этой причине приведённая оценка завышена. Дальнейшие рассуждения исключают подсчёт одних и тех же строк несколько раз.
В статье найдена вероятность того, что fuck встретится хотя-бы один раз. На самом деле мне казалось, что и описание, и содержание явно об этом говорят, может быть мне стоило более аккуратно выбирать формулировки. Касательно Вашего предыдущего вопроса про код - на привычной мне Java это было бы str.contains("fuck").
На шаге 2 получена приблизительная формула, и я даже вкратце объяснил почему. Точное значение отличается от приблизительного, пусть и не очень сильно. Пожалуйста, прочитайте немного дальше прежде чем судить, спасибо!
ребята, занимаясь с конструктором, вынуждены искать не технические решения возникшей проблемы, которые как раз и развивают их инженерную мысль, а нужные детальки
Погодите, так разве не ограниченный набор деталей заставляет быть более креативным в инженерных решениях? Я в детстве с одним жалким "ЛИГО" чего только не собирал. Набор деталей в Education серии намеренно делают очень гибким, чтобы что угодно можно быть сделать. А опыт получается из сборок по инструкции, чтобы потом работать уже без неё.
(фу блин, не в той ветке ответил)
Тут нигде нет вложенных доказательств от противного. Есть две посылки в одном доказательстве.
Окей, в доказательстве, которое я привёл, посылка одна.
В рамках исходной посылки, канторовое число сформулировано в форме брадобрея. Его не может существовать не из-за исходной посылки, а из-за формулировки. Поэтому оно ничего не доказывает.
Нет, там приводится вещественное число, удовлетворяющее всем аксиомам вещественных чисел, конструктивно и неоспоримо. Оно существует по построению =) Противоречие возникает не с существованием данного числа, а с существованием соответствующего отображения из R в N.
Метод состоит в оценке вероятности того, что случайный объект из заданного класса удовлетворяет нужному условию. Если доказано, что эта вероятность положительна, то объект с нужными свойствами существует. Хотя доказательство использует вероятности, окончательный вывод делается определённо, без какой-либо неоднозначности.
Говорю же, неуместно.
Существование такого перебора, собственно, и доказывает счётность числа элементов. Существование хоть чего-то несчётного доказать не получится без привлечения абсурдных определений.
Т.е. согласно вашим рассуждениям, вы априори считаете, что все бесконечные множества (которые содержат счётное подмножество) счётны сами по себе. А доказательство несчётности множества вещественных чисел считаете абсурдом, при этом не указав, что именно там абсурдно. Точнее так — вы указали на часть, кажущуюся вам абсурдной, я привёл контраргумент, уточняющий доказательство Кантора, в который вы, кажется, не захотели вдумываться.
Ничего не мешает. Только доказательство Тьюринга разваливается.
Намекаете на специальные завершающие состояния? Их наличие или отсутствие не влияет на исследуемые свойства.
Произвольный объём памяти. Выделенное — это квантор всеобщности, ключевая часть доказательства по индукции.
Стараюсь понять, что вы имеете ввиду. Бесконечная лента и лента заданного неограниченно большого размера — совершенно разные вещи, если вы об этом. Второе — не интересно в рамках проблемы останова.
Докажите.
Из доказательства той же проблемы останова следует, что задача эквивалентности программ тоже неразрешима. Невозможно по программе понять, использует ли она какую-то конкретную "подпрограмму" или нет.
Понятие остановимости не применимо к некорректным программам.
Что такое некорректная программа? Любой набор команд для машины Тьюринга является корректной программой, каким бы бессмысленным он ни был. Машина STOP, кажется вы её так назвали, корректна по построению, если предполагать, что машина HALT существует, что являлось базой доказательства от противного.
Попробую разобраться. Я честно вдумываюсь в то, что вы пишете, поверьте. Итак, Если HALTS существует, то есть противоречие. Значит утверждение "HALTS существует" либо ложно, либо абсурдно, либо неоднозначно.
Полагаю, вы сравниваете такую машину с бородобреем, но немного теряется суть. Существование бородобрея приводит к его несуществованию. Существование же машины HALTS приводит к логическому противоречию, не утверждающему невозможность существования HALTS. И, в отличие от бородобрея, утверждение о несуществовании HALTS к противоречию не приводит, по крайней мере математика таких противоречий до сих пор не знает.
Далее, "абсурдность" и "неоднозначность". Неоднозначности быть не может, так как ложность исключена. Наверное поэтому вы её не упомянули. Остаётся исключить абсурдность.
Итак, есть утверждение: "существует объект, удовлетворяющий данному формальному свойству", которое не может быть истинным. Является ли оно абсурдным? На мой взгляд только в том случае, если его ложность приводит к противоречию. Это самый скользкий момент в ваших рассуждениях, на самом деле, ведь не до конца понятно, что значит "абсурдно" с формальной точки зрения.
Т.е., подводя итог, если исходить из предположения, что непротиворечивость теории алгоритмов в объединении с принятым утверждением о проблеме останова не доказана формально, то выходит, что истинность проблемы останова пока принимать рано, верно? То же касается любых теорем существования. Это определённо любопытный взгляд на математику. Думаю, вам просто сразу следовало сказать, что вы из тех, кто принципиально отрицает доказательства от противного, стало бы проще. В рамках данных убеждений ваш вывод уже имеет больше смысла, но, к сожалению, такая математика оказывается гораздо скучнее, ведь многие теоремы становятся недоказуемыми, или как минимум не имеют известных конструктивных доказательств. Кажется я наконец вас понял.
Тем не менее, то, что вы пишете про счётность множества вещественных чисел, даже при этих допущениях абсолютно неадекватно. При переборе надо доказывать не только то, что перебрали бесконечное множество элементов, а то, что перебрали все элементы. А этого вы не показали.
P.S. Про теорию вероятностей. Думаю вы имеете представление о том, что она строится на теории мер и что значением вероятности являются вещественные числа от 0 до 1. И то, что для непрерывных распределений требуется интегрирование и т.д. Это я к чему? Применять аппарат теории вероятностей к тому, на чём эта теория строится, немного рекурсивно, не находите?
У меня так много вопросов… я опущу обсуждение большей части видео и сосредоточусь на мощности множества вещественных чисел и проблеме останова.
"Опровержение" доказательства Кантора — бред. Доказывать от противного, используя внутри доказательство от противного — абсолютная норма. Почитайте доказательство теоремы Менгера, например, там гораздо менее абстрактно. Плюс у Кантора не доказывается, что есть вещественное число, которое не вещественное. Краткий пересказ настоящего доказательства:
предполагаем, что есть отображение C: R -> N, определённое на всех вещественных чисел и такое, что для разных аргументов результатом будут разные натуральные числа;
строим конкретное вещественное число, основываясь на этом отображении;
доказываем, что отображение C не определено на нём, что приводит к противоречию со свойствами C.
Что вас тут не устроило?
Ваше доказательство того, что вещественных чисел вполне может быть счётное количество — тоже бред. Притягивание за уши теории вероятностей и понятий вроде "мат ожидание" неуместно. На чём строится ваше доказательство в итоге? Перескажу, как я понял: выбирая бесконечное количество раз случайные вещественные числа, мы с вероятностью 1 в итоге выберем каждое из них. Кажется вы это утверждали. НО, осуществлять перебор, например используя мат индукцию, можно только для счётного количества элементов. Откуда тогда взялось число 1, если мера любого счётного подмножества равна 0? Вам формализма в рассуждениях не хватает. Это и доказательством то не назовёшь. Выглядит как "если предположить, что множество счётно, то оно счётно". Окей.
Теперь по поводу Тьюринга. Первое — что мешает выразить троичные ответы через двоичный код и рассматривать именно такой подкласс алгоритмов? Причём тут вообще классическая логика, не понимаю.
Теперь, "существовать он вполне может" — это как? Что значит "бросить ошибку"? Завершение с ошибкой — нормальное свойство машин Тьюринга, если в текущем состоянии не найдена команда, соответствующая символу на ленте. Они только так и завершаются, добавление специального состояния принципиально ничего не поменяет.
Анализатор, проверяющий выход "за границы памяти" — ровно то, что вы описали. Диапазон памяти конечен, алфавит конечен, размер программы конечен. Так что запускаем и ждём либо повторения конфигурации, либо выхода за границы. Один из этих вариантов обязательно случится за конечное время.
Другое дело, что такой анализатор ничем не поможет ввиду неограниченности ленты, о чём вы тоже сказали. Зачем тогда была вся заключительная часть?
"Алгоритм некорректен, так как его поведение зависит от результата работы анализатора" — такое свойство банально невычислимо. Вы тоже стараетесь придумать какой-то хак, ведь вам наверное просто не нравится то, что проблема останова неразрешима.
Да и вообще, завершение с ошибкой == остановка, разве нет. Скажите, какой третий вариант можно добавить к паре "остановится / не остановится"? Число шагов либо конечно, либо бесконечно, третьего быть не может, даже если добавить абсурдные и невозможные утверждения.
Скажите, вы обсуждаемые доказательства из науч-поп источников узнавали или действительно знакомы с их математическими формулировками и формальными доказательствами? Ставлю на то, что вы не сможете мне рассказать, что такое машина Тьюринга.
Извиняюсь за такой большой комментарий, меня просто задевает подобная безграмотность.
Кажется, значение результата сильно преувеличивают. Плюс автор оригинальной статьи явно лукавит — то ему не нужна оригинальная матрица, чтобы найти собственные вектора (это в общем случае являлось бы явной ложью), то уже вдруг матрица должна быть эрмитовой и нужно знать собственные числа минорных матриц, а это значения, явно зависящие от самой матрицы, не только от её собственных чисел.
Как уже было сказано в предыдущих комментариях, многое в статье вводит в заблуждение. Грустно, при большей внимательности к математическим деталям могла бы получиться действительно интересная статья, но вышла, увы, обычная жёлтая пресса.
В вашей версии игры, по какой-то причине, можно переписывать числа в конец даже тогда, когда ещё есть другие доступные ходы. Получается, что у вас другой набор правил, который я никогда не рассматривал. Так что да, при этом условии может существовать более короткое решение, верю.
Решение ушло слишком далеко по строкам — отметаем, возвращаемся к другой ветке.
Собственно, я так и поступал.
Это, пмсм, не самое верное решение. Так будет найден локальный минимум.
Знаю, именно поэтому после нахождения первого попавшегося решения я перебирал все более короткие ветки, чтобы узнать, не пропустил ли чего. В начале у меня приоритет в очереди был по другому признаку и первым было найдено решение в 86 цифр.
Наверное, нужно было отразить это в тексте, спасибо!
Так у меня и так перебор на очереди с приоритетами) Только не до конца уверен, что имеется ввиду под обрезкой ветвей. Это как если просто ограничить количество ходов?
Я так понимаю, для данной функции стоит вопрос — чему будет равен результат halts(f, (f, halts), halts) (т.к. у f теперь два входных параметра, я явно описал их как пару). Во всяком случае, такой вопрос должен ставиться. Но давайте делать так, как вы предлагаете, и рассмотрим вариант halts(f, (f, ?), ()). Что бы он собой не представлял.
Далее, я предполагаю, что синтаксис (0) означает функцию, тождественно равную константе 0. Я наверное пропустил, где вводится такое обозначение, но да ладно, из контекста можно догадаться. Значение пустых скобок мне, кстати, не ясно.
после этого функция halts(f, f_param, ()) будет анализировать две функции: f(f_param, 0) и f(f_param, 1).
Опять что-то с обозначениями) Будем разбираться: halts(f, (f, ?), ()) делает внутри себя 2 вызова: halts(f, (f, ?), (0)) и halts(f, (f, ?), (1)). В таком виде получается полная бессмыслица, ибо последний параметр в halts по идее в данном "контексте" просто игнорируется. Наверное, имелось ввиду halts(f, (f, (0)), ()) и halts(f, (f, (1)), ()). Тут хоть можно что-то вычислять. Итого — первое выражение равно 1, второе — 0. Потому что f(f, (0)) остановится, а f(f, (1)) — нет.
Буду честен — я действительно старался понять, что вы собираетесь с этим делать дальше, но не смог. На этом моменте я сдаюсь. Какой должен быть ответ и как вы его собираетесь получить?
Кажется, что вы и сами сильно запутались и перестали понимать, где производится запуск функции, а где анализ (исходя из ваших замечаний о рекурсии). Да и суть доказательства вы потеряли. Вместо того, чтобы показать, что контрпример приводит к противоречию, вы стараетесь показать, что какой-то другой пример к противоречию не приведёт. Мне так показалось.
Я советую спокойно, с листочком и ручкой, определить все сигнатуры всех функций, которые вы предлагаете, далее сформулировать анализируемую функцию, её предполагаемые параметры, механизм подстановки (0) и (1) и то, что с этим потом делать. Тщательно всё это проанализировать и уже потом делать выводы. Сейчас же в ваших рассуждениях слишком много несостыковок и их слишком сложно понять из-за отсутствия внятно введённых понятий.
максимально полная частичная функция эквивалентности
… может быть весьма общим решением?
Весьма размытые понятия. Ясное дело, что в частных случаях или для определённых классов функций можно доказывать эквивалентность, но в общем случае — нет.
"Функции, вызывающее противоречие" — это инструмент доказательства от противного. В реальности же все рассматриваемые алгоритмы всегда детерминированы. Соответственно, противоречий в них никаких нет.
Мне потребуется немного времени, чтобы дать вам развёрнутый ответ. Добавлю его в эту ветку комментариев.
Пока лишь скажу - перед тем как обвинять кого-то в незнании основ, пожалуйста, убедитесь на 100%, что сами не ошиблись.
Вы посчитали часть слов несколько раз, т.е. ваше вычисление - неточное
Остальное городить к тому, что вы ошиблись. Это сказано и в статье, и в комментариях. Данную ошибку уже совершили несколько людей. Ваш вариант считает некоторые слова по несколько раз, в частности слова, которые содержат fuck 2 и более раз. Так что могу лишь попросить быть внимательнее
Реальная вероятность дана в пункте 3.1, равна 0.00003720064..., вычислена по рекуррентной формуле. Дальше идёт общий случай
Как раз таки нет, Rsa97 не прав. В приблизительном решении слово
"fuckfuckfuckfuckfuck"(5 раз, ровно 20 букв) будет учтено 5 раз вместо одного, именно по этой причине приведённая оценка завышена. Дальнейшие рассуждения исключают подсчёт одних и тех же строк несколько раз.В статье найдена вероятность того, что fuck встретится хотя-бы один раз. На самом деле мне казалось, что и описание, и содержание явно об этом говорят, может быть мне стоило более аккуратно выбирать формулировки.
Касательно Вашего предыдущего вопроса про код - на привычной мне Java это было бы
str.contains("fuck").На шаге 2 получена приблизительная формула, и я даже вкратце объяснил почему. Точное значение отличается от приблизительного, пусть и не очень сильно. Пожалуйста, прочитайте немного дальше прежде чем судить, спасибо!
Погодите, так разве не ограниченный набор деталей заставляет быть более креативным в инженерных решениях? Я в детстве с одним жалким "ЛИГО" чего только не собирал. Набор деталей в Education серии намеренно делают очень гибким, чтобы что угодно можно быть сделать. А опыт получается из сборок по инструкции, чтобы потом работать уже без неё.
(фу блин, не в той ветке ответил)
Окей, в доказательстве, которое я привёл, посылка одна.
Нет, там приводится вещественное число, удовлетворяющее всем аксиомам вещественных чисел, конструктивно и неоспоримо. Оно существует по построению =) Противоречие возникает не с существованием данного числа, а с существованием соответствующего отображения из R в N.
Метод состоит в оценке вероятности того, что случайный объект из заданного класса удовлетворяет нужному условию. Если доказано, что эта вероятность положительна, то объект с нужными свойствами существует. Хотя доказательство использует вероятности, окончательный вывод делается определённо, без какой-либо неоднозначности.
Говорю же, неуместно.
Т.е. согласно вашим рассуждениям, вы априори считаете, что все бесконечные множества (которые содержат счётное подмножество) счётны сами по себе. А доказательство несчётности множества вещественных чисел считаете абсурдом, при этом не указав, что именно там абсурдно. Точнее так — вы указали на часть, кажущуюся вам абсурдной, я привёл контраргумент, уточняющий доказательство Кантора, в который вы, кажется, не захотели вдумываться.
Напомните, в каком месте оно разваливается?
Намекаете на специальные завершающие состояния? Их наличие или отсутствие не влияет на исследуемые свойства.
Стараюсь понять, что вы имеете ввиду. Бесконечная лента и лента заданного неограниченно большого размера — совершенно разные вещи, если вы об этом. Второе — не интересно в рамках проблемы останова.
Из доказательства той же проблемы останова следует, что задача эквивалентности программ тоже неразрешима. Невозможно по программе понять, использует ли она какую-то конкретную "подпрограмму" или нет.
Что такое некорректная программа? Любой набор команд для машины Тьюринга является корректной программой, каким бы бессмысленным он ни был. Машина STOP, кажется вы её так назвали, корректна по построению, если предполагать, что машина HALT существует, что являлось базой доказательства от противного.
Попробую разобраться. Я честно вдумываюсь в то, что вы пишете, поверьте. Итак, Если HALTS существует, то есть противоречие. Значит утверждение "HALTS существует" либо ложно, либо абсурдно, либо неоднозначно.
Полагаю, вы сравниваете такую машину с бородобреем, но немного теряется суть. Существование бородобрея приводит к его несуществованию. Существование же машины HALTS приводит к логическому противоречию, не утверждающему невозможность существования HALTS. И, в отличие от бородобрея, утверждение о несуществовании HALTS к противоречию не приводит, по крайней мере математика таких противоречий до сих пор не знает.
Далее, "абсурдность" и "неоднозначность". Неоднозначности быть не может, так как ложность исключена. Наверное поэтому вы её не упомянули. Остаётся исключить абсурдность.
Итак, есть утверждение: "существует объект, удовлетворяющий данному формальному свойству", которое не может быть истинным. Является ли оно абсурдным? На мой взгляд только в том случае, если его ложность приводит к противоречию. Это самый скользкий момент в ваших рассуждениях, на самом деле, ведь не до конца понятно, что значит "абсурдно" с формальной точки зрения.
Т.е., подводя итог, если исходить из предположения, что непротиворечивость теории алгоритмов в объединении с принятым утверждением о проблеме останова не доказана формально, то выходит, что истинность проблемы останова пока принимать рано, верно? То же касается любых теорем существования. Это определённо любопытный взгляд на математику. Думаю, вам просто сразу следовало сказать, что вы из тех, кто принципиально отрицает доказательства от противного, стало бы проще. В рамках данных убеждений ваш вывод уже имеет больше смысла, но, к сожалению, такая математика оказывается гораздо скучнее, ведь многие теоремы становятся недоказуемыми, или как минимум не имеют известных конструктивных доказательств. Кажется я наконец вас понял.
Тем не менее, то, что вы пишете про счётность множества вещественных чисел, даже при этих допущениях абсолютно неадекватно. При переборе надо доказывать не только то, что перебрали бесконечное множество элементов, а то, что перебрали все элементы. А этого вы не показали.
P.S. Про теорию вероятностей. Думаю вы имеете представление о том, что она строится на теории мер и что значением вероятности являются вещественные числа от 0 до 1. И то, что для непрерывных распределений требуется интегрирование и т.д. Это я к чему? Применять аппарат теории вероятностей к тому, на чём эта теория строится, немного рекурсивно, не находите?
У меня так много вопросов… я опущу обсуждение большей части видео и сосредоточусь на мощности множества вещественных чисел и проблеме останова.
"Опровержение" доказательства Кантора — бред. Доказывать от противного, используя внутри доказательство от противного — абсолютная норма. Почитайте доказательство теоремы Менгера, например, там гораздо менее абстрактно. Плюс у Кантора не доказывается, что есть вещественное число, которое не вещественное. Краткий пересказ настоящего доказательства:
Что вас тут не устроило?
Ваше доказательство того, что вещественных чисел вполне может быть счётное количество — тоже бред. Притягивание за уши теории вероятностей и понятий вроде "мат ожидание" неуместно. На чём строится ваше доказательство в итоге? Перескажу, как я понял: выбирая бесконечное количество раз случайные вещественные числа, мы с вероятностью 1 в итоге выберем каждое из них. Кажется вы это утверждали. НО, осуществлять перебор, например используя мат индукцию, можно только для счётного количества элементов. Откуда тогда взялось число 1, если мера любого счётного подмножества равна 0? Вам формализма в рассуждениях не хватает. Это и доказательством то не назовёшь. Выглядит как "если предположить, что множество счётно, то оно счётно". Окей.
Теперь по поводу Тьюринга. Первое — что мешает выразить троичные ответы через двоичный код и рассматривать именно такой подкласс алгоритмов? Причём тут вообще классическая логика, не понимаю.
Теперь, "существовать он вполне может" — это как? Что значит "бросить ошибку"? Завершение с ошибкой — нормальное свойство машин Тьюринга, если в текущем состоянии не найдена команда, соответствующая символу на ленте. Они только так и завершаются, добавление специального состояния принципиально ничего не поменяет.
Анализатор, проверяющий выход "за границы памяти" — ровно то, что вы описали. Диапазон памяти конечен, алфавит конечен, размер программы конечен. Так что запускаем и ждём либо повторения конфигурации, либо выхода за границы. Один из этих вариантов обязательно случится за конечное время.
Другое дело, что такой анализатор ничем не поможет ввиду неограниченности ленты, о чём вы тоже сказали. Зачем тогда была вся заключительная часть?
"Алгоритм некорректен, так как его поведение зависит от результата работы анализатора" — такое свойство банально невычислимо. Вы тоже стараетесь придумать какой-то хак, ведь вам наверное просто не нравится то, что проблема останова неразрешима.
Да и вообще, завершение с ошибкой == остановка, разве нет. Скажите, какой третий вариант можно добавить к паре "остановится / не остановится"? Число шагов либо конечно, либо бесконечно, третьего быть не может, даже если добавить абсурдные и невозможные утверждения.
Скажите, вы обсуждаемые доказательства из науч-поп источников узнавали или действительно знакомы с их математическими формулировками и формальными доказательствами? Ставлю на то, что вы не сможете мне рассказать, что такое машина Тьюринга.
Извиняюсь за такой большой комментарий, меня просто задевает подобная безграмотность.
Кажется, значение результата сильно преувеличивают. Плюс автор оригинальной статьи явно лукавит — то ему не нужна оригинальная матрица, чтобы найти собственные вектора (это в общем случае являлось бы явной ложью), то уже вдруг матрица должна быть эрмитовой и нужно знать собственные числа минорных матриц, а это значения, явно зависящие от самой матрицы, не только от её собственных чисел.
Как уже было сказано в предыдущих комментариях, многое в статье вводит в заблуждение. Грустно, при большей внимательности к математическим деталям могла бы получиться действительно интересная статья, но вышла, увы, обычная жёлтая пресса.
В вашей версии игры, по какой-то причине, можно переписывать числа в конец даже тогда, когда ещё есть другие доступные ходы. Получается, что у вас другой набор правил, который я никогда не рассматривал. Так что да, при этом условии может существовать более короткое решение, верю.
Собственно, я так и поступал.
Знаю, именно поэтому после нахождения первого попавшегося решения я перебирал все более короткие ветки, чтобы узнать, не пропустил ли чего. В начале у меня приоритет в очереди был по другому признаку и первым было найдено решение в 86 цифр.
Наверное, нужно было отразить это в тексте, спасибо!
Извините, я не понимаю, где вы нашли рекурсию.
А теперь по делу:
Я так понимаю, для данной функции стоит вопрос — чему будет равен результат
halts(f, (f, halts), halts)(т.к. уfтеперь два входных параметра, я явно описал их как пару). Во всяком случае, такой вопрос должен ставиться. Но давайте делать так, как вы предлагаете, и рассмотрим вариантhalts(f, (f, ?), ()). Что бы он собой не представлял.Далее, я предполагаю, что синтаксис
(0)означает функцию, тождественно равную константе0. Я наверное пропустил, где вводится такое обозначение, но да ладно, из контекста можно догадаться. Значение пустых скобок мне, кстати, не ясно.Опять что-то с обозначениями) Будем разбираться:
halts(f, (f, ?), ())делает внутри себя 2 вызова:halts(f, (f, ?), (0))иhalts(f, (f, ?), (1)). В таком виде получается полная бессмыслица, ибо последний параметр вhaltsпо идее в данном "контексте" просто игнорируется. Наверное, имелось ввидуhalts(f, (f, (0)), ())иhalts(f, (f, (1)), ()). Тут хоть можно что-то вычислять. Итого — первое выражение равно1, второе —0. Потому чтоf(f, (0))остановится, аf(f, (1))— нет.Буду честен — я действительно старался понять, что вы собираетесь с этим делать дальше, но не смог. На этом моменте я сдаюсь. Какой должен быть ответ и как вы его собираетесь получить?
Кажется, что вы и сами сильно запутались и перестали понимать, где производится запуск функции, а где анализ (исходя из ваших замечаний о рекурсии). Да и суть доказательства вы потеряли. Вместо того, чтобы показать, что контрпример приводит к противоречию, вы стараетесь показать, что какой-то другой пример к противоречию не приведёт. Мне так показалось.
Я советую спокойно, с листочком и ручкой, определить все сигнатуры всех функций, которые вы предлагаете, далее сформулировать анализируемую функцию, её предполагаемые параметры, механизм подстановки
(0)и(1)и то, что с этим потом делать. Тщательно всё это проанализировать и уже потом делать выводы. Сейчас же в ваших рассуждениях слишком много несостыковок и их слишком сложно понять из-за отсутствия внятно введённых понятий.Для этого понятие алгоритма нужно сужать, а не расширять. К слову — расширить его никто ни разу не смог, см. тезис Чёрча.
Весьма размытые понятия. Ясное дело, что в частных случаях или для определённых классов функций можно доказывать эквивалентность, но в общем случае — нет.
"Функции, вызывающее противоречие" — это инструмент доказательства от противного. В реальности же все рассматриваемые алгоритмы всегда детерминированы. Соответственно, противоречий в них никаких нет.