Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I don't understand the busy beaver stuff, but is this argument similar:

On a 32-bit computer, there are 2^32 bytes of memory or 256^(2^32)=2^34359738368 possible states. A program is something that takes you from one memory state to another and you want to figure out if the state transitions form a cycle?



Similar idea, but with Turing machines rather than physical computers.

Simplified a bit, the n-th busy beaver number is the number of 1s which can be written out by an n-state Turing machine.

For 2-symbols and n-states, the sequence goes: 6, 21, 107, >= 47176870, > 7.4×10^36534, > 10^10^10^10^18705353 — and those inequalities are because the numbers themselves cannot be computed directly, you have to run the program to see what it does.

https://en.wikipedia.org/wiki/Busy_beaver


I think this approach quickly enters the realm of transcomputational problems [1], which, given the limits of this universe is equivalent to "undecidable" for all practical considerations.

[1] https://en.wikipedia.org/wiki/Transcomputational_problem




Consider applying for YC's Summer 2026 batch! Applications are open till May 4

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

Search: