News for hackers. Stuff that matters.
Re:BB(3, 3) is Hard by penteract on Tuesday October 17, 2023 @02:09AM (#37911214)
> you can write programs that only halt if arbitrary mathematical conjectures are true or false

I don't think this is quite right - you can write programs that halt iff arbitrary mathematical conjectures are provable (in a suitable system of logic/axioms such as ZFC), but there are problems (such as questions about Turing machines with a halting problem oracle[0]) for which we can't straightforwardly construct a program which halts iff they are true.

[0] https://en.wikipedia.org/wiki/Oracle_machine#Oracles_and_hal...

There are no comments on this comment yet.