The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
0 votes
As codes of turing machines are unique for a given turing machine,Say no i have two turing machines ,one for even a's and other for odd a's over the input a,b. Now both these machines will have same transition function but different final state and codes of turing machine is the representation of transition function,so how do these two turing machines will have different codes?
asked in Theory of Computation by Boss (23.9k points) | 86 views
As final states are different, so encodings will be different too as an encoding of a TM includes the encoding of its states too.

I was thinking the same,but can you explain the first paragraph in this page,it considers only transitions of TM.


Even if they consider only the transitions of TM, Encoding will be unique. See the Example in the pic carefully.
First 4 bits of the encodings are for states. 

Extract from Peter Linz- 



Check This too.

In stack exchange link they mentioned that we need to consider the complete 7-tuple encoding for TM.I agree with this point.

But in the figure i have attached from hopcraft and the one you have attached from Peter Linz, the binary encoding they have given it is just for the transition function and if i have some machine which has same set of states and same transition function but differ only by final state as i mentioned in question then it is not possible to uniquely identify TM just with transition encoding.Do you agree or am i missing something?
In any 2 TMs If only final state differs then at least one of the transition must differs right?
Say i have two states q1 and q2.q1 and q2 has self loop of b.

q1 on a goes to q2 and q2 on b goes to q1.

Now if q1 is final then even a's

if q2 is final then odd a's.....

Now these are two TM has exact same transitions.

If you are not able to understand please let me know,i can upload pictorial representation of the same.

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

35,535 questions
42,875 answers
42,216 users