/cs/


Start a New Thread


@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 нельзя было так просто наебать.

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

Где я тут ошибаюсь? Я не верю, что я первый кому пришла в голову эта (наверное ошибочная) идея.
15 replies omitted. Click here to view the first page.
@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
По теореме Райса.

719a0 – ``Generic-case complexity''719a0fe8aed94261aefed80410bfac8c

@fb7f3a038bdf4f25b81c62297ed415dc Anonymous 2020-06-23 07:34:28
https://en.wikipedia.org/wiki/Generic-case_complexity
Это что-то стоящее внимания или просто бесполезный и унылый высер передознувшихся от спиртяги пидорах?
> Ilya Kapovich, Alexei Myasnikov, Vladimir Shpilrain, A. Ushakov