Test: Programming Techniques Storage & Subroutines - Computer Science Engineering (CSE) MCQ

A turing machine has finite number of states in its CPU. However the states are not small in number. Real computer consist of registers which can store values (fixed number of bits).

According to the statistics of the question, we will have a finite machine with 2^96 states.

 A move of a turing machine is the function of the state of finite control and the tape symbol just scanned.

 Cartesian product works like a struct in C/C++. For Example: Computer tape storage is something like 8 or 9 bits in each cell. One can recognize a multi track tape machine by looking at the transitions because each will have tuples as the read and write symbols.

The 6-tuple (Q, X, S, d, q0, F) can be explained as:
Q represents finite set of states,
X represents the tape alphabet,
S represents the input alphabet
d represents the relation on states and the symbols
q0 represents the initial state
F represents the set of final states.

In a n-track turing machine, one head reads and writes on all the tracks simultaneously.

This can be generalized for n- tracks and can be proved equivalent using ennumerable languages.

In automata theory, a formal language is called recursively ennumerable language or partially decidable or semi decidable or turing acceptable or turing recognizable if there exists a turing machine which will ennumerate all valid strings of the language.

Recursively Ennumerable languages are type 0 languages in the Chomsky hierarchy. All regular, context free, context sensitive languages are recursivelyennumerable language.