As final states are different, so encodings will be different too as an encoding of a TM includes the encoding of its states too.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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?

+1

As final states are different, so encodings will be different too as an encoding of a TM includes the encoding of its states too.

0

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

0

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-

0

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?

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?

0

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.

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.

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.7k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.4k
- CO & Architecture 2.9k
- Computer Networks 3.3k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 482
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,861 questions

47,532 answers

145,982 comments

62,293 users