[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.


More information about the SeqFan mailing list