- 1
- 2
- 3
(x) {
if F(x,x) then { for(;;) }
}-
Куча / Говнокод #20110
−17
http://www.michurin.net/computer-science/halting-problem.html
Неразрешимость проблемы остановки имеет много доказательств. В терминах функций её очень просто доказать от противного.
Допустим, у нас уже есть решение — функция F, которая принимает на вход некую функцию (вернее строку с текстом функции, байт-кодом или иной записью функции) и некие данные и отвечает на вопрос: «остановится ли функция-первый-аргумент, при работе с данными-вторым-аргументом, или будет работать вечно?»
Давайте создадим функцию P(x), такого вида (на C-образном языке):
P(x) {
if F(x,x) then { for(;;) }
}
Строку, которая кодирует эту функцию обозначим p. Что будет, если мы вызовем функцию F(p,p)? Возможны два исхода:
True, если P останавливается. Но при этом P(p) как раз не останавливается, если F(p,p)=True, то запускается бесконечный цикл.
False, если P зависает. Но, как не трудно видеть, именно в этом случае P(p) не зависнет.
Мы получили противоречие потому, что наша начальная посылка о существовании магической функции F была не правильной.
Получается, что задача останова неразрешима. Вернее, нельзя написать программу, которая бы решала эту задачу. Иными словами, нельзя написать парсер программного кода, который бы мог оценить, зависнет разбираемый код или нет.
В данном доказательстве на довольно глубинном уровне зарыто говно. Подробности в комментарияхЗапостил:
j123123,
01 Июня 2016
Follow us!
Допустим, есть программа А, которой доступны 10 кб оперативной памяти, регистры процессора и сам процессор. Как узнать, зависает ли программа A? Очень просто: пишем программу Б, которая бы эмулировала 10 кб оперативной памяти и процессор с регистрами, загружаем туда нашу программу. На каждом "шаге" виртуального процессора, программа делает дамп оперативной памяти и регистров процессора и сравнивает этот дамп с теми дампами, которые уже записаны. Если этот дамп ни с одним другим не совпадает, то мы этот дамп записываем. Если дамп совпадает с более ранним дампом, то мы обнаружили зависание.
Что касается доказательства неразрешимости, которое приведено в вашей заметке, то тут все очень просто: программа Б внутри программы Б обнаружит, что ей явно нехватает оперативной памяти для эмуляции самой себя, а дальше все ясно.
К сожалению, такой способ проверки зависания не подходит для доказывания существования или несуществования нечетных совершенных чисел. На машине Тьюринга такая проверка будет работать далеко не всегда. Если реализовать программу, проверяющую зависания описанным выше способом, то такая программа никогда не обнаружит зависания этого:
a=2
while ( (a % 2) == 0)
{
a=a+2
}
если рост переменной a ничем не ограничен. Но человеку, понимающему смысл этой записи и знающему основы математики, вполне понятна причина зависания. Четное число + четное число это всегда четное число. Если верить тезису Чёрча-Тьюринга, то существует программа на машине Тьюринга, способная прийти к выводу, что эта программа зависает, поскольку человек вполне способен к нему прийти. Таким образом, чтобы обнаружить это зависание, программа ндолжна уметь делать какие-то рассуждения, а не просто выполнять некоторую программу, в надежде что ее состояние повторится или она остановится.
a - конечный набор инструкций тестируемой программы
b - параметры, которые мы передаем тестируемой программе
И пусть она возвращает true если ф-ция не останавливается, и false если останавливается. Впрочем, это не важно.
Сделаем функцию В(a):
B(a) {
Б(a,a);
}
Что будет, если мы вызовем В(В)?
Давайте смотреть по шагам:
В(В) вызывает Б(В,В)
Б(B,B) эмулирует работу В(В):
#В(В) вызывает Б(B,B)
#Б(B,B) эмулирует работу В(В):
##В(В) вызывает Б(B,B)
##Б(B,B) эмулирует работу В(В):
...
И мы понимаем, что оно зависло, эмулируя само себя. Эта самоэмуляция никогда не остановится, потому что эмулируемая функция сама эмулирует саму себя и так до бесконечности, состояние первоначально эмулируемой функции никогда не повторится, потому что внутри эмулируемой функции будет еще эмуляция, внутри ней еще и так до бесконечности. Если мы поняли что оно зависло и если верить тезису Чёрча-Тьюринга, то должен существовать алгоритм, который это зависание способен обнаружить. Как бы он его стал обнаруживать? Хороший вопрос. Видимо, так же как и мы: пошагово выполнять тестируемую программу (эмуляция) и смотреть, не происходит ли внутри тестируемой программы эмуляции. Если происходит, то не повторяет ли эмулируемая внутри программы программа тот код, который уже обрабатывался? Иными словами, не эмулируется ли эмулятор, который эмулирует сам себя до бесконечности? Допустим, функция, обнаруживающая такого рода зависания это П(a,b).
a - конечный набор инструкций тестируемой программы
b - параметры, которые мы передаем тестируемой программе
П(В,В) эмулирует работу В(В):
#В(В) вызывает Б(B,B)
#Б(B,B) эмулирует работу В(В):/1
**STOP**
Внутри функции В(В) началась эмуляция В(В)
Условия остановки эмуляции /1 никогда выполнены не будут, будет разрастание В(В) которая себя внутри себя бесконечно эмулирует и не может остановиться.
Теперь сделаем функцию Вп(a):
Bп(a) {
П(a,a);
}
Запустим Bп(Вп)
Вп(Вп) вызывает П(Вп,Вп)
П(Bп,Bп) эмулирует работу Вп(Вп): /1
#Вп(Вп) вызывает П(Вп,Вп)
#П(Bп,Bп) эмулирует работу Вп(Вп): /2
**STOP**
А вот это уже интересно. Что тут происходит? П(Вп,Bп) /1 эмулирует функцию Вп(Вп), которая запускает П(Вп,Bп) /2. Что должна сделать функция П(Вп,Bп) /1 ? Если ф-ция П(Bп,Bп) /1 "решила" что это зависает, тогда П(Bп,Bп) /1 завершает работу, но точно так же должна будет поступить функция П(Bп,Bп) /2. Если функция П(Bп,Bп) /2 так поступит, то П(Bп,Bп) /1 должна обнаружить это, и сообщить что это не зависает т.к. П(Bп,Bп) /2 завершилось. Это очень похоже на http://ru.wikipedia.org/wiki/Парадокс_Рассела
А разгадка на самом деле проста. Функция П(Вп,Bп) /1 должна сообщить, что это зависает, и при этом *зависнуть*. Тогда никаких противоречий нет, потому что П(Bп,Bп) /2 поступит так же. Если нет возможности так сделать, то Bп(Вп) просто зависнет
А теперь рассмотрим доказательство неразрешимости проблемы остановки, описанное в вашей этой заметке:
Сделаем функцию Впб(a):
Bпб(a) {
if (ПБ(a,a)) { for(;;) }
}
Что будет, если мы вызовем функцию ПБ(Bпб,Bпб)? Давайте посмотрим
ПБ(Bпб,Bпб) эмулирует работу Впб(Впб): /1
#Впб(Впб) проверяет условие для if
#Для этого Впб(Впб) вызывает ПБ(Bпб,Bпб)
#ПБ(Bпб,Bпб) эмулирует работу Впб(Впб): /2
**STOP**
Функция ПБ(Bпб,Bпб) /1 обнаружила, что она эмулирует функцию Впб(Впб), которая вызывает ПБ(Bпб,Bпб) /2 которая эмулирует функцию Впб(Впб) итд. Ситуация аналогична предыдущей, и тут у нас такое же решение. ПБ(Bпб,Bпб) /1 должна сообщить что это зависает, и сама при этом она должна зависнуть, тогда никаких противоречий тут нет, и доказательство неразрешимости проблемы остановки, описанное в вашей в вашей заметке, является неверным потому что оно основано на предположении что программа, проверяющая зависание, должна обязательно завершиться при обнаружении зависания или независания. Не учитывается варианта, что такая программа может сообщить о зависании, но при этом зависнуть. Если же она обязательно должна завершаться как только обнаружит зависание, то такая программа просто зависнет в такой ситуации, при этом она "поймет" что она зависла, но сообщить она об этом не может, потому что если она об этом сообщит, то она должна не зависнуть.
она уже давно решена, в том смысле что это теоретическая проблема и к реальному нетеоретическому железу просто неприменима.
А насколько простой будет сама задача сравнения дампа со всеми более ранними? Не «зависнет» ли программа на сравнениях?
Зато задачу остановки реальной машины всегда можно решить на машине тьюринга с бесконечной лентой.
Я заглянул в машинный зал и посмотрел, как работает энергогенератор. Институт не зависел от городских источников энергии. Вместо этого, после уточнения принципа детерминизма, решено было использовать хорошо известное Колесо Фортуны как источник даровой механической энергии. Над цементным полом зала возвышался только небольшой участок блестящего отполированного обода гигантского колеса, ось вращения которого лежала где-то в бесконечности, отчего обод выглядел просто лентой конвейера, выходящей из одной стены и уходящей в другую. Одно время было модно защищать диссертации на уточнении радиуса кривизны Колеса Фортуны, но поскольку все эти диссертации давали результат с крайне невысокой точностью, до десяти мегапарсеков, Учёный совет института принял решение прекратить рассмотрение диссертационных работ на эту тему вплоть до того времени, когда создание трансгалактических средств сообщения позволит рассчитывать на существенное повышение точности.
Несколько бесов из обслуживающего персонала играли у Колеса – вскакивали на обод, проезжали до стены, соскакивали и мчались обратно. Я решительно призвал их к порядку. «Вы это прекратите, – сказал я, – это вам не балаган».
Стругацкие, «Понедельник начинается в субботу».
Это греет меня долгими холодными зимними вечерами...
— Конечно, ловушка, — ответил Дейника. — И называется она «уловка двадцать два». «Уловка двадцать два» гласит: «Всякий, кто пытается уклониться от выполнения боевого долга, не является подлинно сумасшедшим».
Да, это была настоящая ловушка. «Уловка двадцать два» разъясняла, что забота о себе самом перед лицом прямой и непосредственной опасности является проявлением здравого смысла. Орр был сумасшедшим, и его можно было освободить от полетов. Единственное, что он должен был для этого сделать, — попросить. Но как только он попросит, его тут же перестанут считать сумасшедшим и заставят снова летать на задания. Орр сумасшедший, раз он продолжает летать. Он был бы нормальным, если бы захотел перестать летать; но если он нормален, он обязан летать. Если он летает, значит, он сумасшедший и, следовательно, летать не должен; но если он не хочет летать, — значит, он здоров и летать обязан. Кристальная ясность этого положения произвела на Йоссариана такое глубокое впечатление, что он многозначительно присвистнул.
Ограничен размером оперативной памяти. Поэтому да, для любой программы с заданным размером оперативной памяти можно сказать остановится она или нет.
А вот для машины тьюринга с бесконечной лентой и других машин без заданного ограничения памяти проблема остановки неразрешима.
> Если мы поняли что оно зависло и если верить тезису Чёрча-Тьюринга, то должен существовать алгоритм, который это зависание способен обнаружить.
Смешная шутка. Можно так запутать программу что мы точно не поймем что она что-то там эмулирует, с чего это алгоритм должен понять.
> Не учитывается варианта, что такая программа может сообщить о зависании, но при этом зависнуть.
Этот вариант невозможен. Если программа нам что-то сообщает, то конечно мы ее остановим и не будет продолжать. Ну и в чем говно доказательства то?
Может быть. Только доказательство какое-то дырявое. Ну вот конкретная программа, которой сказали эмулировать саму себя эмулирующую себя эмулирующую себя и так до бесконечности, она МОЖЕТ понять что тут дело неладно, так что тут есть над чем подумать
>Можно так запутать программу что мы точно не поймем что она что-то там эмулирует, с чего это алгоритм должен понять.
Надо делать как можно более прозрачную эмуляцию, чтобы программа могла бы легко выцепить эмуляцию с одной стадии и сравнить ее с другой эмуляцией, делавшейся ранее на меньшем уровне вложенности. А если специально запутывать - надо автоматический распутыватель делать. К тому же доказательство неразрешимости проблемы эквивалентности алгоритмов основано на доказательстве неразрешимости той самой проблемы останова
>Этот вариант невозможен. Если программа нам что-то сообщает, то конечно мы ее остановим и не будет продолжать.
Ну это мы ее остановим, внешнее воздействие
Представь что тебе вот сказали X; Только этот X рекурсивный:
X = "чтобы ты представил сам себя в параллельной вселенной, где бы тебе сказали X и если то что ты представил зависнет то тогда ты подними правую руку, а если оно не зависло и поднимает руку, то ты тогда сам зависни"
А теперь скажи, разве из этого следует что тебя не существует?
Не может конечно. Ей сказали например эмулировать компьютер, на компьютере запустили майнкрафт, в майнкрафте собрали машину тьюринга и на ней запустили эту программу. Как программе понять что они не просто в майнкрафт играют а что-то там эмулировать начали.
Если ты начал делать подобный эмулятор, тебе еще надо бы доказать самому себе, что эта машина тьюринга внутри майнкрафта будет полностью эквивалентна той, которая в ней самой потом будет эмулироваться в последствии. Например, там может внезапно заспавниться крипер и взорвать твою машину тьюринга нафиг. Если это так, если ты это можешь математически доказать, то рано или поздно (но в любом случае за конечное время) программа сможет перелезть через уровни абстракции, пронюхать что там где-то в майнкрафте есть машина тьюринга которая никогда криппером не взрывается и работает вечно, и оказывается что она исполняет то, что в конечном итоге исполняет ту же машину тьюринга, которая саму себя в итоге эмулирует, ну и так далее.
сможет
> оказывается что она исполняет то, что в конечном итоге исполняет ту же машину тьюринга, которая саму себя в итоге эмулирует
не сможет. Например пусть первая машина первым делом выводит "1", а вторая - "11". Тогда эти машины будут разными, она и не догадается что мы на самом деле в майнкрафте сделали чтоб к машине добавлялся вывод единички, на результат зависнет\не зависнет он же не влияет.
Это уже смена изначальной постановки задачи. Но вроде бы нам не важно, что там оно первым делом выводит. Важно понять, зависает эмулируемая штука, или нет. Так что выводимые машиной тьюринга единички можно смело в /dev/null отправлять, если мы ставим задачу доказать зависаемость.
ну так я не смогу узнать зависло оно или нет. Я буду бесконечно долго ждать, а оно будет продолжать и продолжать что-то считать, ни разу не повторяясь.
Надо сопоставления делать, например доказывать что эта штука делает (эмулирует) то, что делала эта же штука 10000 годами ранее (может быть оно там каким-то хитрым образом обфукцсированно из-за пропускания через эмулятор, но это ж можно распутать за конечное время)
Тогда надо попробовать доказать, что такой комбинации в памяти никогда не наступит
>И тогда мне остается только продолжать симуляцию и ждать возникнет ли эта комбинация.
Могут быть и другие способы доказать это. Чисто математическими способами, например теорема Ферма была доказана без всяких переборов (перебором ее можно было б только опровергнуть, это тоже пытались делать, безуспешно).
А могут и не быть. Итого: нам не удалось доказать что возможна машина, которая будет определять что она эмулирует сама себя. Таким образом, исходное доказательство о неразрешимости остается в силе.
Как не удалось доказать и то, что такая машина невозможна
if(эта функция) then поднять else зависнуть.
она зависла, нарушив Х. Я не хочу никаким отладчиком цепляться, я сразу выкидываю эту функцию т.к. она не работает, виснет вместо ответа.
---
> которая может "понять" что она сама себя эмулирует
Внутри себя она может "понимать" что угодно. От нее требуется вернуть правильный результат - а она не возвращает.
Кстати, шесть юзеров пытаются утопить это интересное обсуждение.
Есть ли хоть одна реальная функция, для которой было бы доказано, что мы не можем ни доказать, ни опровергнуть ее зависаемость?
Может быть самой машины тьюринга попросту нет, и потому получается такая нелепая ситуация, когда программа вроде бы способна понять, что от ее выбора зависнуть или не зависнуть зависит то, нужно ли ей будет зависнуть или не зависнуть(зависнуть если не зависнет и не зависать если зависнет). Понятное дело, что на конечной памяти такие трюки не пройдут
Таким образом, любая функция, для которой доказано, что за конечное время мы не можем ни доказать, ни опровергнуть что она зависает, должна на самом деле зависать, да? Конечно же нет, ведь зависание мы как бы не должны уметь доказывать. Следовательно, не существует, такой функции, для которой мы можем доказать, что мы не можем ни доказать ни опровергнуть что она зависает.
Может тут проблема в другом. Может быть та самая функция, для которой нельзя доказать ее зависание, занимает собой всю бесконечную ленту на Машине Тьюринга? Предположим что у нас машина Тьюринга и там есть инструкция NOP которая ничего не делает, и инструкция return 0; Лента бесконечно заполнена только одними NOP-ами, но мы этого не знаем, мы вынуждены искать в этих NOP-ах инструкцию return которая там естественно никогда не встречается, но поскольку мы этого не знаем, мы вынуждены искать return 0 до бесконечности. Поскольку return 0 там нигде нет, программа зависает, но за конечное число инструкций мы не можем доказать отсутствие return 0 на этой ленте
https://ru.wikipedia.org/wiki/Машина_Зенона нужна
> Может быть та самая функция, относительно которой мы нихрена не можем доказать, может ее попросту НЕ СУЩЕСТВУЕТ?
Есть бесконечное множество функций. Теорема утверждает, что мы не можем решить останов для всех. Можем решить для конечного числа функций, можем для каждой второй функции, но все равно останутся те для которых мы проблему не решили.
А есть ли доказательства что среди некоего конечного множества функций(например функций, длины которых не превышают 1000 байт), существует хотя бы одна, для которой проблема останова неразрешима? (вместо 1000 можно подставить какое угодно число, но не бесконечность)
>Вот бесконечная лента (а значит и оперативная память) - да, но машина тьюринга это таблица состояний которая конечна, а лента - просто входные данные.
Бесконечная лента это такая же невозможная в реальном мире штука, как и бесконечная функция. Т.е. это тоже неконструктивно.
>Теорема утверждает, что мы не можем решить останов для всех. Можем решить для конечного числа функций, можем для каждой второй функции, но все равно останутся те для которых мы проблему не решили.
Почему нельзя назвать конкретное конечное множество функций, среди которых гарантированно есть хотя бы 1 функция, для которой доказать что она зависает - невозможно? Существует ли вообще такое множество, если мы не можем его предоставить? Это типа как Бог - он существует, потому что никто не доказал что его нет, но продемонстировать его никто не может?
Я нуб, можете указать на ошибки?#вореции
бесконечная лента - конструктивно. Особенность конструктивной математики в том что она не рассматривает бесконечность актуальную, а только потенциальную. Или как-то так. В общем, она рассматривает конкретно описанные процессы, завершающиеся (или не завершающиеся) за конечное время. Поэтому машина тьюринга которая будет бесконечно печатать единички - вполне конструктивный процесс, да, он не завершается, но все его шаги вполне конкретно описаны. А вот машину с бесконечным число состояний (ака функцию бесконечной длины) описать невозможно, поэтому она не конструктивная. Там еще забавные теоремы есть, например про то что невозможно отличить два вещественных числа (которые тоже могут быть вполне конструктивными объектами).
Насчет конкретной функции - ну ты же сам все сказал. Если мы приведем такую функцию, очевидно будет что она не завершается. Поэтому такую функцию привести невозможно. Важно что всегда будут функции типа поиска совершенных чисел или теоремы ферма, останов которых на данном этапе развития мы решить не можем. А сможем ли когда-нибудь - неизвестно.
gost: функция может не зацикливаться но при этом никогда не останавливаться. Ну или что считать зацикливанием. Например она ищет решение теоремы ферма, если нашла - выходит. Да, в ней будет крутится один и тот же кусок, но содержимое памяти то меняется, рано или поздно она может из него выйти (а по факту не выйдет). Ну или если не нравится теорема ферма и нужно формальное доказательство то можно рассказать опять с начала про функцию которой подают на вход ее саму, и т.д. Просто теорема ферма\другие задачи теории чисел удобный пример чтоб показать что это за функции такие.
Пронумеруем бесконечное счётное множество состояний машины натуральным числом N. Пусть при считывании нолика машина переходит в предыдущее состояние (если она не находится в состоянии 0), а при считывании единички - в следующее.
Описал же :)
Машина с бесконечным числом состояний и функция бесконечной длины это совсем не одно и то же. Состояние ж в памяти хранится. Ну да ладно. Вот например вполне можно на брейнфаке с бесконечной лентой написать эмулятор брейнфака с бесконечной лентой который бы параллельно (на брейнфаке можно реализовать многозадачность) запускал и исполнял бы все возможные программы на брейнфаке, и при времени t стремящемуся к бесконечности, число состояний тоже будет стремиться к бесконечности.
И функцию бесконечной длины описать тоже возможно, например можно сделать функцию, которая бы в stdout выводила бы функцию бесконечной длины.
>Насчет конкретной функции - ну ты же сам все сказал. Если мы приведем такую функцию, очевидно будет что она не завершается. Поэтому такую функцию привести невозможно.
Тут даже все немного сложнее. Можно доказать, что для любого конечного множества программ, выполняемых на машине Тьюринга с бесконечной памятью, существует программа X, не входящая в это множество, которая может точно сказать относительно любой из этих программ, какая из них завершиться, а какая нет.
Ч.Т.Д.
bormand: уговорил. я не помню почему именно конечное. придется сослаться на определение машины тьюринга - там по определению конечное число состояний. Для описанной тобой машины с бесконечным числом можно построить эквивалентную с конечным числом состояний.
j123123: Угу. А для произвольной машины тьюринга мы это доказательство провести не сможем.
https://ru.wikipedia.org/wiki/Парадокс_Рассела
> Единственному деревенскому брадобрею приказали: «Брить всякого, кто сам не бреется, и не брить того, кто сам бреется». Должен ли брадобрей брить самого себя?
Переведя эту формулировку в терминах функций:
> Функции приказали «Зависать при получении в stdin функции, которая сама не зависает, и не зависать, если функция зависает». Должна ли функция зависать на самой себе, пытающейся решить, зависать ли ей если ей передать саму себя, пытающуюся решить (ну и так далее рекурсивно)?
Получается, что Тьюринг своим доказательством нихуя нового не открыл, это было и до него(парадокс рассела открыт раньше неразрешимости проблемы останова), просто он выразил это в других терминах
Парадокс лжеца тоже логически эквивалентен этому
см. также http://avva.livejournal.com/2122436.html
Вообще-то я только что доказал, что для любой реально существующей программы конечной длины существует программа, которая бы давала правильный ответ на вопрос "зависнет ли эта программа"
Что же касается доказательства неразрешимости. Давай рассмотрим гипотетический брейнфак-контроллер в котором под ленту с инструкциями брейнфака отведено 100 байт и под ленту с памятью отведено тоже 100 байт. Берем мегамногоядерный кластер и перебираем все возможные кобенации всех брейнфак программ, влезающих в контроллер, получаем в итоге таблицу поиска: массив из 2^(100*8) бит, в которой 0 отмечена зависающая и 1 отмечена независающая программа на брейнфаке. Все что описано до этого момента вполне возможно сделать. Для простоты будем считать что сам брейнфак-контроллер не имеет никаких портов ввода-вывода, может только сделать return 0; в самом конце работы(если не зависнет);
теперь напишем (переведем в брейнфак) следующий код
if(X) for{;;};
return 0;
где X это битик, который соответствует ответу в той таблице поиска на вопрос, зависает ли та же самая программа if(X) for{;;} return 0;
Вот в этом-то и наёбка! Есть две программы
if(1) for{;;};
return 0;
if(0) for{;;};
return 0;
Первая зависает, вторая нет, и доказывается это элементарно. А подставить туда именно такой битик, чтобы он правильно предсказывал зависаемость этой же самой программы - это невозможно чисто математически.
> Вообще-то я только что доказал, что для любой реально существующей программы конечной длины существует программа, которая бы давала правильный ответ на вопрос "зависнет ли эта программа"
ну да. для любой МТ мы можем взять две машины, одну возвращающую 0 и вторую возвращающую 1 и сказать, что одна из них точно дает правильный ответ насчет того останавливается наша МТ или нет. Но вот определить какая именно мы не можем.
> Что же касается доказательства неразрешимости. Давай рассмотрим гипотетический брейнфак-контроллер в котором под ленту с инструкциями брейнфака отведено 100 байт и под ленту с памятью отведено тоже 100 байт.
Если у него память ограничена, то легко можно составить таблицу, но программа проверяющая таблицу не влезет в эту память и поэтому для нее в таблице битика не будет. Поэтому он принципиально отличается от случая рассмотренного в теореме останова, соответственно непонятно что ты хочешь для него доказать.
Но мы не можем и доказать, что мы не можем определить, какая именно.
>Если у него память ограничена, то легко можно составить таблицу, но программа проверяющая таблицу не влезет в эту память и поэтому для нее в таблице битика не будет. Поэтому он принципиально отличается от случая рассмотренного в теореме останова, соответственно непонятно что ты хочешь для него доказать.
Нам не важно что оно в эту память не влезло. Нас интересует всего один битик из той таблицы, который точно в память влезет, не имеет значения, какими средствами мы его вычислили.
Важно то, что НЕТ такого битика X который правильно отвечал бы на вопрос о зависаемости "if(X) for{;;} else return 0;", который если подставить его в "if(X) for{;;} else return 0;" являлся бы битиком 1 если эта же программа не зависала, и являлся бы битиком 0 если бы эта программа зависала, это самопротиворечиво.
Это говорит о том, что нет такой конечной компьютерной программы, которая будучи подставлена вместо X и заинлайнена (специализирована как у турчина) правильно бы отвечала на это.
Это говорит также о том, что нам нужно нечто большее по возможностям по отношению к самой программе (или некоему множеству программ) если мы хотим доказывать что-то в отношении них. Оно не должно быть "засовываемым" в эту самую функцию "if(X) for{;;} else return 0;". Например, для машины тьюринга с памятью бесконечной длины это может быть что-то сверхтьюринговое, скажем машина зенона. Для машины тьюринга с конечной длиной памяти это будет машина тьюринга с большим количеством памяти, или с бесконечной памятью. Это кстати уже теорема Гёделя о неполноте...
То что в общем случае не можем - доказали. Про конкретный случай - да, ничего не можем доказать.
Это говорит также о том, что нам нужно нечто большее по возможностям по отношению к самой программе (или некоему множеству программ) если мы хотим доказывать что-то в отношении них.
Не что-то, а именно проблему останова. Разны другие вещи можно и без этого доказывать - например что существует машина тьюринга которая зависает или что любая машина или зависает или не зависает.
Ну и т.к. мы считает что множество машин тьюринга эквивалентно любой другой созданной человеком формы представления алгоритмов, то мы доказывем эти утверждения для всех алгоритмов вообще. Да, можно придумать "машину зенона" которая бы доказывала останов, но построить ее не удастся. И при этом можно придумать алгоритм (тот же поиск четных совершенных чисел), который машина тьюринга со всей ее бесконечной памятью не поможет нам разрешить.
Этого общего случая не существует, т.к. речь идет о несуществующей машине тьюринга с бесконечной лентой
>Да, можно придумать "машину зенона" которая бы доказывала останов, но построить ее не удастся.
Машину тьюринга с бесконечной лентой построить тоже не удастся. Так что это все сугубо теоретические рассуждения. Нет ничего удивительного в том, что чтобы доказать завершаемость программы на несуществующей машине тьюринга с бесконечной лентой, надо сделать несуществующую машину зенона
Для любой конечной программы на МТ существует правильный ответ на вопрос "зависает ли она", а как его получить - это неважно. В рамках тьюринг-машины за конечное время эта задача нерешаема
Этому случаю соответсвуют вполне существующие задачи типа теоремы ферма или поиска совершенных чисел.
В этом и интерес машин тьюринга - любой алгоритм можно представить машиной тьюринга и любой машине соответствует алгоритм. Поэтому доказывая что-то мы доказываем свойства любого алгоритма. А если рассматривать машины с конечной памятью то там уже не так интересно, т.к. они описывают только узкий класс собственно вычислительных машин.
Программав КНБ очевидно не может выиграть (для доказательства поставим ее против самой себя). Вот может ли она сыграть хотя бы вничью - более интересный вопрос.
> шагов m может быть бесконечное число, так что мы не сможем денормализировать сумму по N.
ОК. Тогда мы можем использовать теорему Исаева о полупроизводных факториалах графических чисел, представляя N в виде суммы отдельных элементов лямбда-графа H (производного от D), что в конечном итоге приведёт нас к двум вореантам - либо S представим в виде фактор-поля, либо нет. В первом случае, для решения проблемы останова нам придётся перебрать рёбра всё того же лямбда-графа H (коих конечное количество, в отличие от D) и просуммировать их полупроизводные. Если эта сумма нечётная - f не остановится, если чётная - остановится. Во втором же случае, нам придётся ворировть S по осям графа D и лямбда-графа H. Полученная вореация S' будем отображать множество независимых графологических отображений S на D-H. Просуммировав в полученной вореации диагональ комплекса поля, мы опять-таки придём к простому решению: сумма нечётная - функция не остановится, сумма чётная - функция остановится. #вореции
на бесконечное множество. И как там суммировать диагональ?
Методом В. Кобена для независимых полупроизводных лямбда-графов.
> на бесконечное множество
Оно не бесконечно, а ограничено сверху количеством уникальных неориентированных пространственных графов для локализованных поверхностей биективного разделения необратимых изменений кривизны рёбер. #вореции
Так что метод Кобена неконструктивен. Фактически это будет та же машина Зенона, выполняющая бесконечное число операций за конечное время.
Как так? Отображение графа на лямбда-граф в любом случае даёт нам конечное скалярное эрц-поле конечных же полупроизводных лямбда-графов. Метод Кобена к ним очень даже применим. #вореции
А kipar таки понял!
ИИ-шизофреник?
https://bnw.im/p/J7FGGG
Обратите внимание на автора, кстати.
Господа гусары, не обращайте внимания на теги к публикациям.
https://bnw.im/p/FQJJHQ
А каким методом математики вычисляют несобственные интегралы и бесконечные ряды? Ведь в наивном представлении для их вычисления нужно бесконечное количество операций.
> лямбда-графа
Гениально!!! Отличнейший ворециарный экземпляр, прекрасно читается, освежает.
На самом деле "теорема останова" не дает никаких гарантий, что существует хотя бы одна функция, для которой бы невозможно было доказать, зависает она или нет. (точнее не просто функция, а просто некая программа, которая не принимает никаких аргументов извне)
Ну да. Но функций то бесконечное множество, все не передокажешь.
Но пацаны, как всегда, не обратили внимания на это визгливое кукареканье. Пусть кукарекает, что с него взять?
Лиспер — не человек, и сегодня ему предстоит очень трудная ночь. У него уже в течение полутора лет каждая ночь была очень трудной, и теперь его анус был разработан настолько, что он без труда мог спрятать в нём metacircular evaluator https://i.imgur.com/iyviGMz.png
Блять, посоветуйте нормальный хостинг для картиночек, чтобы прямые ссылки были действительно прямыми, как циклы Царя. imgur вместо прямых ссылок теперь перекидывает на говноедство какое-то.
И как оно, пользователи есть, через год не протухнет?