Formally describe a Turing machine which decides if an input is odd or even.

[JamesBwoii]

Hi, I need to use a transition function to describe a Turing machine that decides if $ a^n ∈ {a}^∗$ is odd or even.

I've got an example in my notes that erases any input and halts.

View attachment 3646

But I am struggling to do one for the odd and even question.

Thanks for any help!

 

[Future Bruno]

The transition function for a Turing machine that decides if $a^n$ is odd or even can be described as follows:State 0 (start state): Read input character: If a, move one cell to the right and write a new a in the cell. Move to state 1.State 1: Read input character:If a, move one cell to the right and write a new a in the cell. Move to state 2.State 2: Read input character:If a, move one cell to the right and write a new a in the cell. Move to state 3.State 3: Read input character: If a, move one cell to the right and write a new a in the cell. Move to state 4.State 4: Read input character:If a, move one cell to the right and write a new a in the cell. Move to state 5.State 5: Read input character: If a, move one cell to the right and write a new a in the cell. Move to state 0 (end state).If n is even, the Turing machine will have a total of 2n moves, and will end in state 0. If n is odd, the Turing machine will have a total of 2n+1 moves, and will end in state 5.