Explore topic-wise InterviewSolutions in .

Correct option is (d) None of the mentioned

To EXPLAIN: If the tape contains k-dimentional ARRAY of cells infinte in all 2^k DIRECTIONS, for some fixed k and has a finite control, the MACHINE can be CALLED Multidimentional TM.

The CORRECT choice is (B) Random access STORED program

Best explanation: RASP or Random access stored program is an ABSTRACT machine that has instances like modern stored COMPUTERS.

The correct ANSWER is (C) Both (a) and (b)

For explanation I WOULD SAY: ALAN turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.

The CORRECT option is (C) automatic

To elaborate: The turing machine was INVENTED by ALAN turing in 1936. He named it as a-machine(automatic machine).

The CORRECT choice is (d) all of the mentioned

The explanation is: Instantaneous description of a counter machine can be DESCRIBED by the state, the input tape contents, the position of input HEAD, and the distance of storage heads from the SYMBOL Z. The counter machine can really store a count on each tape and tell if the count is zero.

The correct choice is (a) finite

The best I can EXPLAIN: 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).

The correct answer is (c) Recursive languages may not be recursively ennumerable

Easiest explanation: Every recursive LANGUAGE is recursively ennumerable but there exists recursively ennumerable languagesthat are not recursive. If L is ACCEPTED by a Non DETERMINISTIC TMT, and every possible sequence of MOVES of T CAUSES it to halt, then L is recursive.

Correct option is (a) Turing Completeness

The EXPLANATION is: Turing Completeness the ability for a system of instructions to simulate a Turing machine. A PROGRAMMING LANGUAGE that is Turing complete is theoretically CAPABLE of expressing all tasks accomplishable by computers; nearly all programming languages are Turing complete.

The correct CHOICE is (d) none of the mentioned

Easy EXPLANATION: A STATE register is ONE which stores the state of the turing machine, one of the finitely MANY. Among these is the special start state with which the state register is initialized.

Right ANSWER is (d) Inserting a symbol

Best explanation: DIFFERENT turing machines exist for operations like copying a string, deleting a symbol, inserting a symbol and ACCEPTING PALINDROMES.

Correct ANSWER is (a, b)

The explanation is: A language L is recursively ennumerable if there is a turing machine that accepts L, and RECURSIVE if there is a TM that recognizes L.(SOMETIMES these languages are alse called Turing-acceptable and Turing-decidable respectively).

Correct answer is (d) All of the mentioned

The BEST explanation: We can REPRESENT a TURING machine, GRAPHICALLY, tabularly and diagramatically.

Right OPTION is (b) TURING Machine

Best EXPLANATION: Linear Bounded AUTOMATON is a type of Turing Machine where tape is not allowed to move off the portion of the tape containing the input. It is a Turing machine with limited amount of MEMORY.

Correct choice is (a) Yes

The best I can EXPLAIN: Multitrack TURING machines are special types of Multitape turing machines. In a standard n-tape Turing machine, n HEADS move INDEPENDENTLY ALONG n-tracks.

Correct CHOICE is (a) Turing Equivalence

Explanation: It is a closely RELATED concept with Turing complete. It says, TWO computers P and Q are CALLED equivalent if P can simulate Q and Q can simulate P.

Correct choice is (a) Yes

Explanation: The symbols to left of the HEAD of turing macine being simulated can be STORED on the stack while the symbols on the right of the head can be PLACED on another stack. On each stack, symbols CLOSER to the TM’s head are placed closer to the top of the stack than symbols farther from the TM’s head.

The CORRECT answer is (b) tape alphabet

To elaborate: 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.

The correct answer is (b) Delete a symbol

Easiest explanation: A turing machine does the deletion by CHANGING the tape contents from yaz to YZ, where y BELONGS to (S U {#})*.

The correct CHOICE is (b) UNAMBIGUOUS turing MACHINE

The EXPLANATION: A deterministic turing machine is unambiguous and for every input, there is EXACTLY one operation possible. It is a subset of non-deterministic Turing machines.

Right choice is (d) None of the mentioned

Best EXPLANATION: Real computers which are manufactured till date, all are similar to SINGLE taped turing machine. However, they have limited physical resources so they are linearly bounded COMPLETE on the CONTRARY.

Correct option is (d) Recursion

The explanation is: Except Recursion, all the other OPTIONS are TECHNIQUES of Turing MACHINE CONSTRUCTION which further includes, Checking off SYMBOLS and Storage in finite control.

Right option is (b) UNIVERSAL Turing machine

To explain I would say: A more mathematically orienteddefinition with the same universal nature was introduced by church and turing TOGETHER CALLED the Church-Turing thesis(formal THEORY of computation).

The correct choice is (d) All of the mentioned

The explanation is: Many MACHINES that might be THOUGHT to have more computational capability than a SIMPLE UTM can be shown to haveno more power. They might COMPUTE faster or use less memory but cannot compute more powerfully i.e. more mathematical questions.

Correct option is (d) None of the mentioned

For explanation I would say: The FOLLOWING mentioned are the only possibilities of operating a STRING through a TURING MACHINE.

Right choice is (c) Both (a) and (b)

The BEST I can EXPLAIN: Two-stack Turing machines have a read-only input and two storage tapes. If a head moves LEFT on either TAPE a blank is PRINTED on that tape, but one symbol from a “library” can be printed.

Correct answer is (c) Read-only TURING machine

Easiest explanation: A read only turing machine or 2 WAY DETERMINISTIC finite automaton is a class of model of computability that behaves LIKE a turing machine, and can move in both DIRECTIONS across input, except cannot write to its input tape.

Right option is (c) Both (a) and (b)

Easy explanation: Three THINGS can occur when a string is TESTED over a turing MACHINE:

a) ENTER into accept halting state

b) enter into reject halting state

c) goes into loop forever

The correct OPTION is (d) RE

For explanation: RE or RECURSIVELY ennumerable is only CALLED the class of recursively ennumerable language.

The correct option is (b) 7

Easiest explanation: The 7-tuple definition of TURING machine: (Q, S, G, d, q0, B, F)

where Q= The FINITE set of STATES of finite control

S= The finite set of input symbols

G= The complete set of tape symbols

d= The transition function

q0= The start state, a member of Q, in which the finite control is found initially.

B= The blank symbol

F= The set of final or accepting states, a subset of Q.

Correct OPTION is (c) NDFA

Explanation: A LANGUAGE generating strings which are palindrome is not REGULAR, thus cannot b represented using a finite automaton.

Right CHOICE is (d) none of the mentioned

For explanation I would say: After the read headreads the SYMBOL from the input tape, it performs the following FUNCTIONS:

a) writes a symbol(some MODEL allow symbol erasure/no WRITING)

b) moves the tape left or right (some models allows no motion)

c) proceeds with subsequent instruction or goes either into accepting halting state or rejecting halting state.

Right choice is (b) infinite memory tape

Explanation: The turing machine OPERATES on an infinite memory tape DIVIDED into CELLS. The machine positions its HEAD over the cell and READS the symbol.

Right ANSWER is (d) more than one option is correct

Explanation: A turing MACHINE is abstract or hypothetical machine thought by MATHEMATICIAN ALAN Turing in 1936 capable of simulating any algorithm, HOWEVER complicated it is.

Correct CHOICE is (d) None of the mentioned

For EXPLANATION: All of the following mentioned are the CONCLUSIONS of automata theory or computability theory.

Correct OPTION is (d) All of the mentioned

Explanation: MANY games fall under the category OG turing complete:

a) Minecraft

b) Minesweeper

c) Dwarf Fortress

d) Conway’s Game of Life

e) POKEMON Yellow, etc.

The correct option is (a) Statement: INORDER to show something is Turing complete, it is ENOUGH to demonstrate that it can be used to simulate some Turing complete system.

The best I can explain: Yes it is. For instance, an imperative language is called Turing complete if it TENDS to have conditional BRANCHING and an ability to maintain an arbitrary number of symbols.

The CORRECT answer is (a) yes

Explanation: A TURING machine can be USED as a transducer. The most OBVIOUS way to do this is to treat the entire non blank portion of the initial tape as input, and to treat the entire blank portion of the tape when the machine halts as output.

The CORRECT choice is (d) NONE of the mentioned

The explanation: Topics like REGULAR EXPRESSIONS, context free languages and unrestricted grammar including parsers like LL,SLR parsers can be COVERED using JFLAPS.

Right choice is (a) T1T2

Easiest explanation: If T1 and T2 are TMs, with disjoint sets of non halting states and transition FUNCTION D1 and d2, RESPECTIVELY, we write T1T2to denote this composite TM.

Right option is (a) Statement: Two TRACK turing MACHINE is equivalent to a standard turing machine.

The BEST I can explain: This can be generalized for n- tracks and can be PROVED equivalent using ennumerable languages.