Timeline for Is it provably true/false that for a program, there exists a proof whether it halts or not?

3 events

when toggle format	what		by	license	comment
Jun 7, 2022 at 12:50	comment	added	user21820		@PatrickStevens: You're correct. There is a funny catch though. There seems to be no way to usefully utilize any uncomputable phenomenon except for RNG use. Suppose humans discover a real-world phenomenon that can be utilized to get a function that appears uncomputable. The problem is that absolutely nobody can verify it, so it remains useless. For example, even if someone claims to have found a real-world halting oracle, nobody can verify that it is not simply something that behaves like a deterministic human and takes 2^k seconds to answer "Does P halt on X" where k = len(P)+len(X). =)
Jun 6, 2022 at 21:29	comment	added	Patrick Stevens		Just to clarify: your statement that a mechanical procedure can duplicate a human is basically a form of the Church-Turing thesis, which empirically seems to be true, but is not logically true. It's possible that there is no computable emulation of the "true" physics on which our universe runs, for example, and in such a world it's possible that human thought makes essential use of this noncomputability. It seems very unlikely that this is the case, but it's not impossible.
Jun 5, 2022 at 17:36	history	answered	Douglas	CC BY-SA 4.0