Question

Recall the Turing machine we designed in class. Consider an infinite tape with the following initial state: _ _ _ _word _ _ _ _ Where word is a binary word (i.e. ones and zeros). Right a Turing machine which checks if the word is divisible by 2 or not. Structure your answer as either a state table, or state diagram.

Answer 1

This is siimple, How many remainders you will get when the number is divisible by 2? It's either 0 or 1. So the state diagram will have 2 states in it. When do we say that a number is divisible by 2? When the remainder is 0. So there will be 2 states called q0 and q1. Start with the state q0 and follow this directions.

When you are in q0 there are 2 possibilities.

Possibility-1: Stay in state q0 if the digit is 0

Possibility-2: Move to q1 if the digit is 1.

Similarily when you are in q1 there are 2 possibilities

Possibility-1: Stay in state q1 if the digit is 1

Possibility-2: Move to q0 if the digit is 0.

So, at the end if you are in state q0, it means that the word is divisible by 2. Checkout the state diagram attached. Final output state will be represented with 2 circles which is an accepted state.