which choices are correct? If M is a multi-tape Turing Machine, there is some st
ID: 3767360 • Letter: W
Question
which choices are correct?
If M is a multi-tape Turing Machine, there is some standard Turing Machine, M', that is equivalent to M.
always
sometimes
never
Which of the following statements is NOT true with respect to a Turing Machine?
Once the set of transitions is defined, the Turing machine is restricted to carrying out one particular type of computation
An accepting Turing Machine may not halt.
A membership Turing Machine always halts.
We can always rewrite an accepting Turing Machine as a membership Turing Machine.
A Universal Turing Maching has three tapes.
always
sometimes
never
Which of the following statements is NOT true with respect to the decidability of a problem?
When we state decidability or undecidability, we must know the domain because this may affect the conclusion.
A single instance of a problem is always decidable.
If the result of a computation is always a simple "yes" or "no", we say that the problem is decidable.
The problem of determining whether any given language is regular is decidable.
Consider the function f(n) whose value is the maximum number of moves that can be made by any n-state Turing Machine that halts when started with a blank tape. Which of the following statements is NOT true regarding this problem.
The function is computable.
The transition function has a finite domain and range.
There are only a finite number of such Turing Machines.
Some of these Turing Machines must halt.
If the domain of a problem is finite, then the problem is decidable.
always
sometimes
never
We can decide for a Turing Machine, M, whether a given state, say q, is ever entered when M is applied to a given nonempty string in the input alphabet.
always
sometimes
never
We can determine whether two Turing Machines accept the same language
always
sometimes
never
Which of the following statements is TRUE with respect to a Recursively Enumerable language, L?
L is always recursive as well.
There is always some Turing Machine that accepts L.
There is always a membership algorithm for L
The complement of L is always recursively enumerable.
Which of the following statements is NOT true with respect to countable sets?
If S is an infinite countable set, then its powerset is countable.
The set of all Turing Machines is countable.
The set of all real numbers is not countable.
Some languages are not countable.
Explanation / Answer
If M is a multi-tape Turing Machine, there is some standard Turing Machine, M', that is equivalent to M.
always
Given standard TM M, construct a multitape TM M' such that L(M)=L(M'). ()):
Given n-tape TM M construct a standard TM M' such that L(M)=L(M').
Which of the following statements is NOT true with respect to a Turing Machine?
We can always rewrite an accepting Turing Machine as a membership Turing Machine.
A Universal Turing Maching has three tapes
always
Consider the function f(n) whose value is the maximum number of moves that can be made by any n-state Turing Machine that halts when started with a blank tape. Which of the following statements is NOT true regarding this problem.
The function is computable
If the domain of a problem is finite, then the problem is decidable.
always
Which of the following statements is TRUE with respect to a Recursively Enumerable language, L
There is always some Turing Machine that accepts L
Which of the following statements is NOT true with respect to countable sets?
If S is an infinite countable set, then its powerset is countable.
Which of the following statements is NOT true with respect to countable sets?
Some languages are not countable
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.