one question came across was, given binary sequence a_0, ..., a_{n-1} how many transitions take such when given non-negative integer outputs a_i if < n , 0 otherwise. can assume input starts 1 unless 0.
using https://martinugarte.com/turingmachine/ simulated following turing machines try , idea how many states should take
sequence n=2, 5 transitions
//sequence 0,1 name: sequence init: 1 accept: end one,0 end,0,- one,1 two,_,> two,_ end,1,- two,0 end,0,- two,1 end,0,- sequenced n=3, 8 transitions
//sequence 0,1,0 name: sequence init: 1 accept: end one,0 end,0,- one,1 two,_,> two,_ end,1,- two,0 three,_,> two,1 end,0,- three,_ end,0,- three,0 end,0,- three,1 end,0,- sequence n=4, 11 transitions
//sequence 0,1,0,1 name: sequence init: 1 accept: end one,0 end,0,- one,1 two,_,> two,_ end,1,- two,0 three0,_,> two,1 three1,_,> three0,_ end,0,- three0,0 end,0,- three0,1 end,0,- three1,_ end,1,- three1,0 end,0,- three1,1 end,0,- from i'd guess o(n) states required specify sequence n long. can prove this?
this true induction. take base case n=2, following turing machine can modified work length 2 sequence
//sequence 0,1 name: sequence init: 1 accept: end one,0 end,0,- one,1 two,_,> two,_ end,1,- two,0 end,0,- two,1 end,0,- now inductive step assume works length n , ordered above. if specify them six0101 10101x replace smallest 1 goes end, sorted number transition acts on @ point, instance,
six0101,0 end,0,- acts on 101010. make transition go 3 new transitions, in example go seven01010 on blank output a_n , stop. on 0,1 output 0 , stop. adds 3 transitions turing machine. satisfying inductive step.
in fact proves binary turing machines states needed have upper bound of 3n-1 transitions. can generalized c-character turing machines following upper bound (c+1)n-1
