Write a TM Turing Machine program which decides the set of b

Write a TM (Turing Machine) program which decides the set of binary strings which when interpreted as decimal integers have the values 5+8n, where n=0,1,2,3..... (So these values are 5, 13, 21, 29, 37, 45, ...) ?

Solution

Turing Machine M

Go to end of input (balnk space). Go left

This works as any binary string of form 8n will have last three bits as 000 (this is because 1 <<3 is 8)

And adding 5 (101) will make strings last three bits as 101.

If