#computability on Hacker News

3 stories tagged computability, newest first.

Screenshot of arxiv.org: Monoidal computer I: Basic computability by string diagrams (2012)

Monoidal computer I: Basic computability by string diagrams (2012)(arxiv.org)

3 points by measurablefunc 3 days ago | 0 comments

arXiv abstract page for Dusko Pavlovic's 2012 paper proposing a model of computation based on monoidal categories and string diagrams.

category-theory string-diagrams monoidal-categories computability

Screenshot of github.com: BB(10) > Graham's Number

BB(10) > Graham's Number (github.com)

62 points by surprisetalk 13 days ago | 46 comments

GitHub markdown analysis of a 10-state Turing machine shown to run at level f_(ω+1) of the fast-growing hierarchy, implying BB(10) exceeds Graham's number.

busy-beaver turing-machines grahams-number fast-growing-hierarchy

Screenshot of quantamagazine.org: With fifth busy beaver, researchers approach computation's limits

With fifth busy beaver, researchers approach computation's limits (quantamagazine.org)

496 points by LegionMammal978 2 years ago | 127 comments

Quanta Magazine article on how a collaborative team of amateur programmers proved the value of the fifth busy beaver number, BB(5).

busy-beaver turing-machines computability theoretical-computer-science

#computability on Hacker News

Monoidal computer I: Basic computability by string diagrams (2012)(arxiv.org)

BB(10) > Graham's Number(github.com)

With fifth busy beaver, researchers approach computation's limits(quantamagazine.org)

BB(10) > Graham's Number (github.com)

With fifth busy beaver, researchers approach computation's limits (quantamagazine.org)