News for hackers. Stuff that matters.
Re:BB(3, 3) is Hard by kmeisthax on Tuesday October 17, 2023 @12:50AM (#37910754)
Sort of. Uncomputable functions exist because the halting problem exists. So any function whose definition includes anything to do with halting also becomes uncomputable. e.g. BB is uncomputable because you have to determine all the TMs that would halt given n and m.

The entire rest of mathematics is smuggled into BB via the halting problem: you can write programs that only halt if arbitrary mathematical conjectures are true or false, so anything that wants to solve the halting problem or solve BB has to be able to know all maths[0]. Of course, this is possible because Turing-completeness is the boundary of computability. Anything that can have a computer in it is itself a computer.

[0] This isn't actually the thing that makes halting undecidable. Undecidability comes from programs that "pull themselves into the halting problem" by only halting if a hypothetical halting problem decider would claim that they don't halt.

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...

Re:BB(3, 3) is Hard by luc4 on Tuesday October 17, 2023 @04:00PM (#37920730)
> Uncomputable functions exist because the halting problem exists.

Uncomputable functions exist because there are only countably many Turing machines. There are problems that stay uncomputable even if the halting problem were computable.