I am new to Turing Machines. As in I’ve been reading about them over the last two days. So I am not very knowledgeable at this moment.
I was also reading about the Kleene’s O system of ordinal notations, in its definition, there is a statement that involves lexicographically ordering Turing Machines. My question is:
How are they ordered?
Thanks
As the comments have said, which order you use doesn't matter, just the fact that there is one. First you have to clearly define your notation for a Turing machine.
One approach I have seen is as follows:
A state of a Turning machine is defined as a tuple $(n,w0,m0,s0,w1,m1,s1)$ where
$n$ is the state number
$w0$ is the character written to the tape if there was a $0$ present
$m0$ is the direction to move the tape one space if there was a $0$ present
$s0$ is the state to go to if there was a $0$ present
and similarly for the items with a $1$ for when there was a $1$ present. By convention we always start at state $0$.
A Turing machine is a tuple of states where the state numbers are in sequential order starting from $0$.
Now there is an obvious lexicographic order. The first character is always $0$ because we have required that. We put all the machines where state $0$ has $w0=0$ before those with $w0=1$. Within each of those groups we put the ones with $m0=L$ before those with $m0=R$. We then break ties the value of $s0$ and so on.
Usually in this area we don't order functions, we order machines. There are lots of machines that add two numbers. Once you have one that works, you can add more states at the end without changing anything because the new states are never used. These machines each come somewhere in the order, but we have no way to pick out all the equivalent "adding machines".