1A formal definition of a standard deterministic Turing Machine involves a tuple of how many elements?
A.5
B.8
C.7
D.6
Correct Answer: 7
Explanation:
A standard TM is defined as a 7-tuple: .
Incorrect! Try again.
2In the 7-tuple definition of a Turing Machine , what does represent?
A.The transition function
B.The set of states
C.The tape alphabet
D.The input alphabet
Correct Answer: The tape alphabet
Explanation:
is the finite set of allowable tape symbols, which includes the blank symbol and the input alphabet .
Incorrect! Try again.
3The transition function of a standard deterministic Turing machine maps from?
A.
B.
C.
D.
Correct Answer:
Explanation:
The transition function takes the current state and the current tape symbol as input, and outputs the next state, the symbol to write on the tape, and the direction to move the head (Left or Right).
Incorrect! Try again.
4What represents an Instantaneous Description (ID) or configuration of a Turing Machine?
A.
B.
C.
D.
Correct Answer:
Explanation:
An ID is represented as , where is the current state, is the tape contents to the left of the head, and is the tape contents from the head onwards.
Incorrect! Try again.
5Which of the following data structures conceptually represents the memory of a Turing Machine?
A.An infinite tape divided into cells
B.A finite set of registers
C.A Last-In-First-Out (LIFO) stack
D.A First-In-First-Out (FIFO) queue
Correct Answer: An infinite tape divided into cells
Explanation:
A Turing Machine uses an infinite (or semi-infinite) tape divided into discrete cells as its primary memory.
Incorrect! Try again.
6A Turing Machine that computes a mathematical function (e.g., addition or multiplication) rather than just accepting or rejecting a language is known as:
A.A linear bounded automaton
B.A recognizer TM
C.A universal TM
D.A transducer TM
Correct Answer: A transducer TM
Explanation:
A TM acting as a transducer computes functions by reading an input string and halting with the function's output written on its tape.
Incorrect! Try again.
7Which of the following languages requires a Turing Machine to be recognized and cannot be recognized by a Pushdown Automaton?
A.
B.
C.
D.
Correct Answer:
Explanation:
is a context-sensitive language and requires at least a Linear Bounded Automaton or a Turing Machine, whereas the others are context-free or regular.
Incorrect! Try again.
8In a standard Turing Machine, when does the machine halt?
A.When it reaches the start state again
B.When it writes a blank symbol
C.When is undefined for the current state and tape symbol
D.When it reaches the end of the input string
Correct Answer: When is undefined for the current state and tape symbol
Explanation:
A Turing Machine halts when it enters a configuration for which no valid transition is defined.
Incorrect! Try again.
9What is the computational equivalence between a single-tape Turing Machine and a multi-tape Turing Machine?
A.Multi-tape TMs are strictly more powerful
B.Multi-tape TMs can solve undecidable problems
C.They are equivalent in computing power
D.Single-tape TMs are strictly more powerful
Correct Answer: They are equivalent in computing power
Explanation:
Any multi-tape TM can be simulated by a single-tape TM, meaning they recognize the exact same class of languages (Recursively Enumerable).
Incorrect! Try again.
10If a Non-Deterministic Turing Machine (NDTM) accepts a language , which of the following is true?
A. must be decidable in polynomial time
B.No DTM can accept
C. must be regular
D.There exists a standard Deterministic Turing Machine (DTM) that also accepts
Correct Answer: There exists a standard Deterministic Turing Machine (DTM) that also accepts
Explanation:
NDTMs and DTMs are equivalent in terms of computability. Any NDTM can be simulated by a DTM (e.g., using a BFS of the nondeterministic computation tree).
Incorrect! Try again.
11What is an "offline" Turing Machine?
A.A TM with a read-only input tape and separate read-write work tapes
B.A TM without a power supply
C.A TM that halts immediately
D.A TM that does not use a tape alphabet
Correct Answer: A TM with a read-only input tape and separate read-write work tapes
Explanation:
An offline TM is a variation that restricts the input tape to be read-only and uses additional tapes for read-write operations (work tapes).
Incorrect! Try again.
12A Universal Turing Machine (UTM) is best described as:
A.A machine that accepts all regular languages
B.A machine that operates in polynomial time
C.A Turing Machine that can simulate the behavior of any other Turing Machine on any given input
D.A machine with an infinite number of states
Correct Answer: A Turing Machine that can simulate the behavior of any other Turing Machine on any given input
Explanation:
A UTM takes a description of a TM and an input , and simulates executing on .
Incorrect! Try again.
13What is a Linear Bounded Automaton (LBA)?
A.A Turing Machine whose tape head can only move right
B.A TM that uses only one state
C.A Pushdown Automaton with two stacks
D.A Non-deterministic Turing Machine with restricted tape size proportional to the input length
Correct Answer: A Non-deterministic Turing Machine with restricted tape size proportional to the input length
Explanation:
An LBA is restricted such that its tape head cannot move beyond the boundaries of the input string (plus optional end markers).
Incorrect! Try again.
14According to the Chomsky Hierarchy, which class of languages is accepted by a Linear Bounded Automaton?
A.Type 1 (Context-Sensitive Languages)
B.Type 2 (Context-Free Languages)
C.Type 0 (Recursively Enumerable Languages)
D.Type 3 (Regular Languages)
Correct Answer: Type 1 (Context-Sensitive Languages)
Explanation:
LBAs are exactly the computational model that recognizes Context-Sensitive Languages (CSLs).
Incorrect! Try again.
15What is the famous "LBA problem" in automata theory?
A.Whether LBAs can recognize regular languages
B.Whether LBAs can simulate TMs
C.Whether LBAs halt on all inputs
D.Whether deterministic LBAs are equal in power to non-deterministic LBAs
Correct Answer: Whether deterministic LBAs are equal in power to non-deterministic LBAs
Explanation:
It remains an open question in theoretical computer science whether DLBA = NLBA (similar to the P vs NP problem, but for LBAs).
Incorrect! Try again.
16Let be the input string of length . The working space of a Linear Bounded Automaton is restricted to:
A.
B.
C.
D.
Correct Answer:
Explanation:
The tape size is restricted to a linear function of the length of the input string, hence .
Incorrect! Try again.
17A cellular automaton consists of a regular grid of "cells". What characterizes the state updates in a standard cellular automaton?
A.States are updated sequentially one by one
B.Only the center cell is updated
C.States are updated randomly
D.States are updated synchronously based on the states of neighboring cells
Correct Answer: States are updated synchronously based on the states of neighboring cells
Explanation:
In a cellular automaton, all cells evaluate their new state simultaneously based on a local transition rule applied to their neighbors.
Incorrect! Try again.
18Conway's Game of Life is a classic example of:
A.A finite state machine
B.A non-deterministic pushdown automaton
C.A 1-dimensional cellular automaton
D.A 2-dimensional cellular automaton
Correct Answer: A 2-dimensional cellular automaton
Explanation:
The Game of Life operates on an infinite two-dimensional orthogonal grid of square cells, each in one of two possible states (alive or dead).
Incorrect! Try again.
19The computational power of standard Cellular Automata (like Rule 110 or Game of Life) is:
A.Equivalent to Finite Automata
B.Turing Complete (Equivalent to a Turing Machine)
C.Equivalent to Pushdown Automata
D.Equivalent to Linear Bounded Automata
Correct Answer: Turing Complete (Equivalent to a Turing Machine)
Explanation:
Both Rule 110 and the Game of Life have been proven to be Turing complete, meaning they can simulate any Turing Machine.
Incorrect! Try again.
20What does the Halting Problem state?
A.It is undecidable whether an arbitrary Turing Machine halts on a given input
B.Turing Machines cannot run infinite loops
C.Every Turing Machine will eventually halt
D.It is impossible to build a Turing Machine
Correct Answer: It is undecidable whether an arbitrary Turing Machine halts on a given input
Explanation:
Alan Turing proved in 1936 that a general algorithm to determine if any given TM halts on any given input cannot exist.
Incorrect! Try again.
21The language is:
A.Recursively Enumerable but not Recursive
B.Not Recursively Enumerable
C.Context-Free
D.Decidable and Recursive
Correct Answer: Recursively Enumerable but not Recursive
Explanation:
The Halting problem is recognizable (we can simulate on and accept if it halts) but undecidable (we cannot guarantee rejection if it loops forever). Therefore, it is RE but not Recursive.
Incorrect! Try again.
22Who originally formulated the Post Correspondence Problem (PCP)?
A.Stephen Cook
B.Alonzo Church
C.Emil Post
D.Alan Turing
Correct Answer: Emil Post
Explanation:
The problem was introduced by Emil Post in 1946 as an undecidable problem that does not explicitly involve Turing machines.
Incorrect! Try again.
23The Post Correspondence Problem (PCP) over an alphabet is known to be undecidable if:
A.The number of dominoes is finite
B.
C.
D.The string length is exactly 2
Correct Answer:
Explanation:
PCP is solvable if the alphabet has only one symbol, but it becomes undecidable for any alphabet containing two or more symbols.
Incorrect! Try again.
24What is the Modified Post Correspondence Problem (MPCP)?
A.A variation of PCP where the sequence must start with the first domino pair
B.A variation of PCP that is decidable
C.A variation of PCP where strings can be reversed
D.A variation of PCP where blank symbols are allowed
Correct Answer: A variation of PCP where the sequence must start with the first domino pair
Explanation:
In MPCP, a valid match must begin with the first specified pair of strings in the list. MPCP is also undecidable.
Incorrect! Try again.
25In Computability Theory, a language is called "Decidable" (or Recursive) if:
A.It requires exponential time to solve
B.It can be generated by a Context-Free Grammar
C.There is a TM that halts on every input and accepts exactly
D.There is a TM that accepts but may loop on strings not in
Correct Answer: There is a TM that halts on every input and accepts exactly
Explanation:
A decidable (recursive) language has a TM that always halts (either accepts or rejects) for every possible input string.
Incorrect! Try again.
26A language is Recursively Enumerable (RE) if:
A.It is decided by a TM that always halts
B.It is a subset of a regular language
C.It is recognized by a TM that may loop infinitely on strings not in the language
D.It cannot be accepted by any TM
Correct Answer: It is recognized by a TM that may loop infinitely on strings not in the language
Explanation:
For RE languages, a TM exists that accepts all valid strings, but it is not guaranteed to halt on invalid strings.
Incorrect! Try again.
27Which of the following statements is TRUE regarding recursive and recursively enumerable languages?
A.All context-free languages are not recursive
B.The complement of a recursively enumerable language is always recursively enumerable
C.Every recursively enumerable language is recursive
D.Every recursive language is recursively enumerable
Correct Answer: Every recursive language is recursively enumerable
Explanation:
If a language is recursive, there is a TM that halts on all inputs. This TM also recognizes the language, so the language is trivially Recursively Enumerable. The converse is false.
Incorrect! Try again.
28If a language and its complement are both Recursively Enumerable, then must be:
A.Context-Free
B.Regular
C.Undecidable
D.Recursive (Decidable)
Correct Answer: Recursive (Decidable)
Explanation:
If both and are RE, we can run their recognizers in parallel. One will eventually halt and tell us if the string is in or , effectively making decidable.
Incorrect! Try again.
29What does the Church-Turing Thesis state?
A.P is not equal to NP
B.Every computable function can be computed by a Turing Machine
C.Deterministic and Non-deterministic TMs are equivalent
D.All languages are recursively enumerable
Correct Answer: Every computable function can be computed by a Turing Machine
Explanation:
The Church-Turing thesis is a hypothesis stating that the intuitive notion of "algorithm" or "computable" is exactly captured by Turing Machines.
Incorrect! Try again.
30The problem of determining whether for a given Turing Machine is called the:
A.Emptiness Problem
B.Halting Problem
C.Equivalence Problem
D.Finiteness Problem
Correct Answer: Emptiness Problem
Explanation:
The Emptiness Problem asks if the language accepted by a TM is empty. This is an undecidable problem.
Incorrect! Try again.
31According to Rice's Theorem, any non-trivial property of the languages recognized by Turing machines is:
A.Recursively Enumerable but not Recursive
B.Polynomial time computable
C.Decidable
D.Undecidable
Correct Answer: Undecidable
Explanation:
Rice's Theorem states that for any non-trivial property of RE languages, it is undecidable whether the language recognized by a given TM satisfies .
Incorrect! Try again.
32Which of the following problems is Decidable?
A.Does a given DFA accept a specific string ?
B.Does a given TM accept all strings?
C.Are two given TMs equivalent?
D.Does a given TM halt on the empty string?
Correct Answer: Does a given DFA accept a specific string ?
Explanation:
The membership problem for Deterministic Finite Automata (DFA) is decidable. All the other options are undecidable problems related to Turing Machines.
Incorrect! Try again.
33The "Blank Tape Problem" (whether a TM halts when started on a blank tape) is:
A.Regular
B.Undecidable
C.NP-Complete
D.Decidable
Correct Answer: Undecidable
Explanation:
The Blank Tape Problem can be reduced from the Halting Problem, making it undecidable.
Incorrect! Try again.
34Time Complexity of a Turing machine computation is measured by:
A.The length of the input string
B.The number of states in the TM
C.The maximum number of tape cells accessed
D.The number of transitions (or steps) the TM makes before halting
Correct Answer: The number of transitions (or steps) the TM makes before halting
Explanation:
Time complexity is defined as the maximum number of steps the machine takes on any input of length .
Incorrect! Try again.
35Space Complexity of a Turing machine computation is measured by:
A.The number of transitions executed
B.The number of final states
C.The size of the tape alphabet
D.The number of distinct tape cells scanned during computation
Correct Answer: The number of distinct tape cells scanned during computation
Explanation:
Space complexity is the maximum number of tape cells that the TM visits while processing an input of length .
Incorrect! Try again.
36In Computational Complexity, the class contains languages that:
A.Cannot be decided by any TM
B.Require exponential time to be decided
C.Can be decided by a Non-Deterministic TM in polynomial time
D.Can be decided by a Deterministic Turing Machine in polynomial time
Correct Answer: Can be decided by a Deterministic Turing Machine in polynomial time
Explanation:
is the class of decision problems solvable by a deterministic Turing machine in time for some constant .
Incorrect! Try again.
37The class stands for:
A.Non-Deterministic Polynomial time
B.Non-Polynomial time
C.Not-Practically computable
D.Negative Polynomial time
Correct Answer: Non-Deterministic Polynomial time
Explanation:
contains decision problems solvable by a Non-Deterministic Turing Machine in polynomial time. Alternatively, problems whose solutions can be verified in polynomial time.
Incorrect! Try again.
38A problem is if:
A. but cannot be verified in polynomial time
B. and is undecidable
C. and every problem in is polynomially reducible to
D. requires exponential space
Correct Answer: and every problem in is polynomially reducible to
Explanation:
NP-Complete problems are the hardest problems in NP. A problem must be in NP and be NP-Hard (all NP problems reduce to it) to be NP-Complete.
Incorrect! Try again.
39The Cook-Levin theorem proved that which of the following problems is NP-Complete?
A.The Halting Problem
B.The Post Correspondence Problem
C.The Boolean Satisfiability Problem (SAT)
D.The Emptiness Problem
Correct Answer: The Boolean Satisfiability Problem (SAT)
Explanation:
Stephen Cook (1971) and Leonid Levin (1973) independently proved that the SAT problem is NP-Complete, the first problem proven to be so.
Incorrect! Try again.
40What is a consequence if it is ever proven that ?
A.Turing machines will become obsolete
B.NP-Complete problems will become undecidable
C.The Halting Problem will become decidable
D.All NP-Complete problems will be solvable in polynomial time by a Deterministic TM
Correct Answer: All NP-Complete problems will be solvable in polynomial time by a Deterministic TM
Explanation:
If P = NP, it means every problem that can be solved by an NDTM in polynomial time can also be solved by a DTM in polynomial time, making all NP problems tractable.
Incorrect! Try again.
41Which of the following relationships between complexity classes is known to be strictly true?
A.
B.
C.
D.
Correct Answer:
Explanation:
Any problem solvable by a DTM in polynomial time is trivially solvable by an NDTM in polynomial time, so P is a subset of NP. Whether it is a proper subset is the P vs NP question.
Incorrect! Try again.
42The class is defined as the set of decision problems solvable by a Turing Machine using:
A.Exponential time
B.Polynomial space
C.Polynomial time
D.Logarithmic space
Correct Answer: Polynomial space
Explanation:
PSPACE is the set of all decision problems that can be solved by a Turing machine using an amount of memory (space) that is polynomial in the size of the input.
Incorrect! Try again.
43Savitch's Theorem states that for any function :
A.
B.
C.
D.
Correct Answer:
Explanation:
Savitch's Theorem proves that a deterministic TM can simulate a nondeterministic TM using at most the square of the space.
Incorrect! Try again.
44An algorithm running in time belongs to which time complexity class?
A.Factorial time
B.Polynomial time
C.Logarithmic time
D.Exponential time
Correct Answer: Exponential time
Explanation:
Functions of the form (where ) represent exponential time complexity, typical of brute-force solutions to NP-Complete problems.
Incorrect! Try again.
45A language is Turing-recognizable. What is another term for Turing-recognizable?
A.Context-Sensitive
B.Recursive
C.Decidable
D.Recursively Enumerable
Correct Answer: Recursively Enumerable
Explanation:
Turing-recognizable means a TM can recognize strings in the language by halting and accepting, which is exactly the definition of Recursively Enumerable (RE).
Incorrect! Try again.
46The busy beaver problem is concerned with:
A.Designing a TM with the minimum number of states
B.Finding the TM that halts the fastest
C.Solving the SAT problem
D.Finding an -state TM that writes the maximum number of 1s on a blank tape and eventually halts
Correct Answer: Finding an -state TM that writes the maximum number of 1s on a blank tape and eventually halts
Explanation:
The Busy Beaver function measures the maximum number of non-blank symbols an -state halting TM can write on a blank tape. This function is uncomputable.
A two-way infinite tape TM can be easily simulated by a standard one-way infinite tape TM (e.g., by folding the tape into two tracks), meaning they recognize the same languages.
Incorrect! Try again.
48In the context of Cellular Automata, "Rule 30" is famous for being:
A.The only rule that halts
B.Capable of generating complex, chaotic patterns often used as a pseudorandom number generator
C.Equivalent to a Finite Automaton
D.Trivial and completely symmetric
Correct Answer: Capable of generating complex, chaotic patterns often used as a pseudorandom number generator
Explanation:
Stephen Wolfram discovered Rule 30, a 1D cellular automaton that generates complex, aperiodic behavior from simple initial conditions, making it useful for random number generation.
Incorrect! Try again.
49The Halting problem is a classic example of a problem that is:
A.Decidable
B.NP-Complete
C.Undecidable but Turing-recognizable
D.Not Turing-recognizable
Correct Answer: Undecidable but Turing-recognizable
Explanation:
We can build a TM to simulate the given TM; if it halts, we accept. Thus it is Turing-recognizable (RE). But we cannot guarantee it will ever halt to reject, making it undecidable.
Incorrect! Try again.
50Which of the following operations is NOT closed for Recursively Enumerable (RE) languages?
A.Concatenation
B.Complementation
C.Union
D.Intersection
Correct Answer: Complementation
Explanation:
RE languages are closed under union, intersection, and concatenation. However, they are NOT closed under complementation (if an RE language's complement is also RE, it becomes recursive/decidable).