On 2 symbols 1-state turning machine, there are 64 posible machines taking into account their transition tables. One of this machines could be: $$A0:0LA$$ $$A1:0RH$$
(meaning: in state A, reading a 0, write 0, goes left and transition to A, in state A, reading a 1, write 0, goes right and halt.)
Another one could be: $$A0:1RA$$ $$A1:0RA$$
Another one: $$A0:1LH$$ $$A1:0RA$$
Assuming we start with a blank tape, only the last one halts. The first just keep going left, and the second just goes right writing 1's.
On 2 symbols 1-state machines, there are 64 posible machines (if we consider transition tables as they source code). But if we consider their behaviour there are only 8 possible outcomes.
- Going Left: $(0L)*$
- Going Right: $(0R)*$
- Going Left writing 1's: $(1L)*$
- Going Right writing 1's: $(1R)*$
- Go left and halt: $0LH$
- Write 1,go left and halt: $1LH$
- Go right and halt: $RH$
- Write 1, go right and halt: $1RH$
(Only the last 4, halt)
For 2 symbols n-state machines:
- The formula for calculating how many machines in terms of transition tables are $(2*2*2*(n+1))^n$? My rational: 2 read symbols, 2 write symbols, 2 directions, (n+1) next states to be defined (independently) in n (running) states
- Is there some kind of standard notation for outcomes?
- Is there a formula for calculating outcomes?
For 2 symbols 2-state machines:
- There are 1296 machines (if my previous formula is ok), but how many outcomes?
- It is known how many of this 1296 halts?