Create accountLogin

Recent searches

No recent searches

Search options

Only available when logged in.
mathstodon.xyz is one of the many independent Mastodon servers you can use to participate in the fediverse.
A Mastodon instance for maths people. We have LaTeX rendering in the web interface!

Administered by:

Server stats:

2.8K
active users

mathstodon.xyz: AboutStatusProfiles directoryPrivacy policy

Mastodon: AboutGet the appKeyboard shortcutsView source codev4.3.7

theHigherGeometer

Hooley dooley.

This post is about a "found-in-the-wild" small Turing machine (3-states, 4-symbols), that halts --- after an Ackermann function-level number of steps; using Knuth's up-arrow notation, more than
14↑↑↑↑↑↑↑↑↑↑↑↑↑↑14
and in fact we know exactly how many!

sligocki.com//2024/05/22/bb-3-

sligocki · BB(3, 4) > Ack(14)Pavel has found a 3-state 4-symbol TM which can compute an “Ackermann-level” function and halts with exactly
May 24, 2024, 08:56 AM·Public
15boosts·32favorites
Public
theHigherGeometer

For a very poor sense of scale, the practically insignificant by comparison 3↑↑↑3 is a power tower of 3s with 7 625 597 484 987 (i.e. over seven and half *trillion*) levels!

SearchLive feeds
About