/cs/


28c8328c8363c0c3c4a6dbf274d7e9aa441e5 – ``Halting problem. Контекст выполнения.''

@8519026881514a27a573812a0d2e42eb fulmar 2021-09-08 03:38:31
https://en.wikipedia.org/wiki/Halting_problem#Sketch_of_rigorous_proof
Имеем g(i) = if h(i, i) then 0 else loop_forever и e - номер программы g.
Какой бы ответ h(e, e) не дала, правильным будет именно тот, который будет противоположен тому, что даст программа h.
Этот трюк возможен только потому, что h не знает в каком контексте она выполняется. Если бы она знала, что она выполняется внутри программы g, то она могла бы дать другой ответ: противоположный тому, что она даёт в пустом контексте (т.е. когда её выполняют напрямую, а не внутри какой-то другой функции). Тогда бы h нельзя было так просто наебать.

Поэтому у каждой программы должен всегда быть дополнительный неявный параметр - контекст выполнения, который представляет собой код всей программы внутри которой выполняется данная программа.

Где я тут ошибаюсь? Я не верю, что я первый кому пришла в голову эта (наверное ошибочная) идея.
@be7d6358956e4122b068f425ff1465dd fulmar 2021-09-08 03:45:28
g(i) = if h(i, i) == 0 then 0 else loop_forever
fix
@d9dd585d8c2a41439d973529dc2d7b8e fulmar 2021-09-08 19:17:33
Парадокс лжеца ("это высказывание ложно") можно разрешить таким же образом, только тут вместо программ будут предикаты.
Имеем Tr(X) - предикат истинности, G(X) = !Tr(X) и A = G(A).
Какой бы ответ Tr(A) не дал, правильным будет противоположный ответ.
Поэтому каждый предикат должен иметь неявный параметр - контекст высказывания. И тогда значение предиката может отличаться в завимости от контекста. Например, значение Tr(A) в контексте "!Tr(A)" должно быть противоположым значению Tr(A) в пустом контексте.
@fbcf3404c1fa4a6783e5b7efccc7494e fulmar 2021-09-08 20:16:21
C теоремой Гёделя о неполноте ("это высказывание не доказуемо") такая же ситуация.
Имеем предикат Pr(y, x), который говорит, что число y есть номер доказательства высказывания с номером x. И предикат G(x) = forall y, !Pr(y, x).
Тут тоже просто за счёт того, что Pr(y, x) имело бы разное значение в разных контекстах, можно было бы разрешить эту проблему.
@af25fb55bdc6487992a6023dfa20b9fa fulmar 2021-09-08 20:46:30
Короче говоря, идея в том, что истинность элементов высказывания может зависеть от этого высказывания. Например, в высказывании A or B и в высказывании A and B (где A в обоих высказываниях идентичны) A может иметь разное значение просто потому что A or B и A and B - это разные высказывания.

Мы даём высказываниям доступ к информации, которая им раньше (в классических формализациях логики) не была доступна.
@560f36bda54c48d799b7d8f5a59f5448 fulmar 2021-09-08 20:57:15
Например, A = "я второй член дизъюнкции". Тогда False or A будет истинно, но A or False будет ложно.
@64660aae3b044846b13c1d2bf0455a59 fulmar 2021-09-08 20:58:59
В классических формализациях подобное невозможно никак выразить.
@4edc9f069815480a8e0bd9aff6f6802a fulmar 2021-09-10 09:39:21
>Где я тут ошибаюсь?
Всё, я понял где ошибка. Для любой программы h можно же построить программу h0, которая будет себя вести точно так же как h в пустом контексте. Тогда в g просто можно использовать h0 вместо h.
@40abf97e704d4dc8a2624912c6cbb075 fulmar 2021-09-11 11:04:23
Теперь у меня другой вопрос.

Относительно любой программы h, множество всех программ можно разделить на два подмножества: программы, которые не содержат внутри себя h или эквивалентную ей программу (две программы эквивалентны если они вычисляют одну и ту же функцию) и программы, которые содержат.

Может ли тогда h быть решением halting problem для первого подмножества?
@0484bd5394824b67a2d4fa7560e37e72 fulmar 2021-09-11 12:02:25
@40abf@40abf97e704d4dc8a2624912c6cbb075 Нет, не может.
Внутри g вместо h можно взять любую не эквивалентную ей программу f такую, что только для значения e h(e, e) = f(e, e).
@342acd30730442198b2ee19b5b2b9b85 fulmar 2021-09-11 12:18:35
Или так не выйдет? Мы e узнаем только после того как определим g, а тут получается мы его должны знать до того как определим g. Хм, похоже тогда этот аргумент не работает.
@c74f5e2746dd451b86d14c4ef4d9dfec fulmar 2021-09-11 12:39:01
А, ну тогда вот такой сработает.
Внутри g вместо h можно взять любую не эквивалентную ей программу f такую, что forall x, h(x, x) = f(x, x). Т.е. их значения будут совпадать только по диагонали, а любые другие могут отличаться.
@cf017a8ea9ab41f2bbc148a81cb15c65 fulmar 2021-09-11 12:45:09
Но вопрос, а существует ли подобная f, которая не будет содержать внутри себя h?
@32e22cb80aba4eaeb6feb73bef33f264 fulmar 2021-09-11 13:54:11
Вообще говоря, такое может быть. Программа h может состоять из трёх независимых подпрограмм:
h(i, j) = if i == j then hd(i, j) else if i > j then ha(i, j) else hb(i, j).
Тогда f может не содержать в себе всю h, а только hd.

Но тогда и @40abf@40abf97e704d4dc8a2624912c6cbb075 можно переформулировать следующим образом.

Относительно любой программы h(i, j), множество всех программ можно разделить на два подмножества: программы, которые не содержат внутри себя hd(i) := h(i, j) или эквивалентную ей программу и программы, которые содержат.

Может ли тогда h быть решением halting problem для первого подмножества?
@5f8d1bfac6264049b646a43dff7974c3 fulmar 2021-09-11 14:03:09
hd(i) := h(i, i)
fix
@a1bb744c14a2400d86abf2cbb9938910 fulmar 2021-09-11 14:54:20
Ладно, понятно, что я хуйнёй занимаюсь, потому что это подмножество, для которого halting problem разрешима, невозможно описать каким-то набором конечных правил, потому что оно не вычислимо.
@374d6db4371f452a9f770d4a57bd0086 fulmar 2021-09-11 14:55:50
*конечным набором правил
@e223a67df0914c94bf87276404268f41 fulmar 2021-09-11 18:35:55
Проблема в том, что у программы может быть сколько угодно эквивалентных или частично эквивалентных ей программ.
@5194673840714944931585b018359905 fulmar 2021-09-12 00:47:26
@a1bb7@a1bb744c14a2400d86abf2cbb9938910
*неразрешимо
fix
По теореме Райса.