[seqfan] Re: Turing machine sequences
israel at math.ubc.ca
israel at math.ubc.ca
Mon Sep 21 23:24:18 CEST 2015
On Sep 21 2015, Allan Wechsler wrote:
>Any well-defined sequence can be expressed as a Turing sequence (this is
>one form of the Church-Turing Thesis), but the minimum number of states
>required to do so provides a sort of measure of how "simple" the sequence
>is. It would be fun to try to produce minimal Turing machines that generate
>classic sequences.
I think you mean every recursive sequence of nonnegative integers can be
expressed as a Turing sequence. The OEIS does include some non-recursive
sequences, e.g. the Busy Beaver A028444 and related sequences.
Cheers,
Robert
More information about the SeqFan
mailing list