1A formal definition of a standard deterministic Turing Machine involves a tuple of how many elements?
A.6
B.8
C.5
D.7
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 tape alphabet
B.The set of states
C.The transition function
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.A First-In-First-Out (FIFO) queue
B.A Last-In-First-Out (LIFO) stack
C.An infinite tape divided into cells
D.A finite set of registers
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 universal TM
C.A transducer TM
D.A recognizer 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 is undefined for the current state and tape symbol
B.When it writes a blank symbol
C.When it reaches the start state again
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 can solve undecidable problems
B.They are equivalent in computing power
C.Multi-tape TMs are strictly more powerful
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.No DTM can accept
B.There exists a standard Deterministic Turing Machine (DTM) that also accepts
C. must be regular
D. must be decidable in polynomial time
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 without a power supply
B.A TM with a read-only input tape and separate read-write work tapes
C.A TM that does not use a tape alphabet
D.A TM that halts immediately
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 with an infinite number of states
B.A Turing Machine that can simulate the behavior of any other Turing Machine on any given input
C.A machine that accepts all regular languages
D.A machine that operates in polynomial time
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 Non-deterministic Turing Machine with restricted tape size proportional to the input length
B.A TM that uses only one state
C.A Turing Machine whose tape head can only move right
D.A Pushdown Automaton with two stacks
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 3 (Regular Languages)
B.Type 1 (Context-Sensitive Languages)
C.Type 2 (Context-Free Languages)
D.Type 0 (Recursively Enumerable 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 halt on all inputs
B.Whether deterministic LBAs are equal in power to non-deterministic LBAs
C.Whether LBAs can simulate TMs
D.Whether LBAs can recognize regular languages
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.Only the center cell is updated
B.States are updated randomly
C.States are updated synchronously based on the states of neighboring cells
D.States are updated sequentially one by one
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 non-deterministic pushdown automaton
B.A 2-dimensional cellular automaton
C.A 1-dimensional cellular automaton
D.A finite state machine
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 Linear Bounded Automata
B.Turing Complete (Equivalent to a Turing Machine)
C.Equivalent to Finite Automata
D.Equivalent to Pushdown 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.Turing Machines cannot run infinite loops
B.It is undecidable whether an arbitrary Turing Machine halts on a given input
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.Decidable and Recursive
B.Context-Free
C.Not Recursively Enumerable
D.Recursively Enumerable but not 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.Alan Turing
B.Emil Post
C.Stephen Cook
D.Alonzo Church
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.
B.
C.The string length is exactly 2
D.The number of dominoes is finite
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 blank symbols are allowed
B.A variation of PCP where the sequence must start with the first domino pair
C.A variation of PCP where strings can be reversed
D.A variation of PCP that is decidable
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.There is a TM that halts on every input and accepts exactly
C.It can be generated by a Context-Free Grammar
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 recognized by a TM that may loop infinitely on strings not in the language
C.It is a subset of a regular 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.Every recursive language is recursively enumerable
B.All context-free languages are not recursive
C.Every recursively enumerable language is recursive
D.The complement of a recursively enumerable language is always 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.Regular
B.Recursive (Decidable)
C.Context-Free
D.Undecidable
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.Deterministic and Non-deterministic TMs are equivalent
B.All languages are recursively enumerable
C.P is not equal to NP
D.Every computable function can be computed by a Turing Machine
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.Equivalence Problem
B.Emptiness Problem
C.Halting 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.Decidable
B.Undecidable
C.Recursively Enumerable but not Recursive
D.Polynomial time computable
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 TM halt on the empty string?
B.Does a given DFA accept a specific string ?
C.Does a given TM accept all strings?
D.Are two given TMs equivalent?
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.NP-Complete
B.Regular
C.Undecidable
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 maximum number of tape cells accessed
B.The length of the input string
C.The number of transitions (or steps) the TM makes before halting
D.The number of states in the TM
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 final states
B.The number of distinct tape cells scanned during computation
C.The number of transitions executed
D.The size of the tape alphabet
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.Can be decided by a Non-Deterministic TM in polynomial time
B.Cannot be decided by any TM
C.Can be decided by a Deterministic Turing Machine in polynomial time
D.Require exponential time to be decided
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-Polynomial time
B.Negative Polynomial time
C.Not-Practically computable
D.Non-Deterministic 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. and is undecidable
B. and every problem in is polynomially reducible to
C. but cannot be verified in polynomial time
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.The Halting Problem will become decidable
B.Turing machines will become obsolete
C.NP-Complete problems will become undecidable
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.Logarithmic space
B.Polynomial time
C.Polynomial space
D.Exponential time
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.Polynomial time
B.Logarithmic time
C.Factorial 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.Recursively Enumerable
B.Context-Sensitive
C.Decidable
D.Recursive
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.Finding an -state TM that writes the maximum number of 1s on a blank tape and eventually halts
B.Solving the SAT problem
C.Designing a TM with the minimum number of states
D.Finding the TM that halts the fastest
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.Trivial and completely symmetric
B.The only rule that halts
C.Equivalent to a Finite Automaton
D.Capable of generating complex, chaotic patterns often used as a pseudorandom number generator
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.Undecidable but Turing-recognizable
B.NP-Complete
C.Not Turing-recognizable
D.Decidable
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.Complementation
B.Union
C.Intersection
D.Concatenation
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).
Incorrect! Try again.
Did this save you a night before the exam?
LPU Notes is free, and it stays free. Ads cover part of the server bill.
The rest comes out of a student's own pocket: the domain, the storage,
and keeping the site up through the weeks everyone needs it at once.
The payment button didn't load. An ad blocker or a filtered network is the usual reason.
to try again.
Nothing here is ever locked, and nothing unlocks. Chip in only if it was worth it.
What it pays for →