Hacker News new | past | comments | ask | show | jobs | submit login

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.




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


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




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: