4 ms·

I quite sympathetic to finitism, even ultrafinitism, but I find Zeilberger's contention to be hard to reconcile with the observation that there is a < 8,000 sta

by tome 3y ago

I quite sympathetic to finitism, even ultrafinitism, but I find Zeilberger's contention to be hard to reconcile with the observation that there is a < 8,000 state (one-tape, two-symbol) Turing machine whose behaviour cannot be proved in ZFC: https://scottaaronson.blog/?p=2725 https://scottaaronson.blog/?p=2725 Maybe Zeilberger would respond that that machine might need to use unbounded amounts of memory. If you fix a bound on memory, i.e. take infinity out of the question, maybe you can't construct such machines.

nsajko 3y ago
> If you fix a bound on memory, i.e. take infinity out of the question, maybe you can't construct such machines. A Turing machine with a tape of only constant length is equivalent to a finite-state automaton. If the length of the tape is a linear function of the length of the input, on the other hand, the machine is a linear bounded automaton. https://en.wikipedia.org/wiki/Linear_bounded_automaton https://en.wikipedia.org/wiki/Linear_bounded_automaton https://en.wikipedia.org/wiki/Finite-state_machine https://en.wikipedia.org/wiki/Finite-state_machine https://en.wikipedia.org/wiki/Template:Formal_languages_and_grammars https://en.wikipedia.org/wiki/Template:Formal_languages_and_...