[seqfan] Re: Turing machine sequences

[israel at math.ubc.ca]

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