2 ms·

Goodstein's Theorem

• peter_d_sherman 3y ago
  >"The Goodstein sequence of a number can be effectively enumerated by a Turing machine; thus the function which maps n to the number of steps required for the Goodstein sequence of n to terminate is computable by a particular Turing machine. This machine merely enumerates the Goodstein sequence of n and, when the sequence reaches 0, returns the length of the sequence. Because every Goodstein sequence eventually terminates, this function is total." An interesting relationship between Goodstein Sequences and Turing Machines!