-
If you are citizen of an European Union member nation, you may not use this service unless you are at least 16 years old.
-
You already know Dokkio is an AI-powered assistant to organize & manage your digital files & messages. Very soon, Dokkio will support Outlook as well as One Drive. Check it out today!
|
Quiz-9
Page history
last edited
by Issa Rice 5 years, 2 months ago
This quiz tests your understanding of computability thery (primitive recursion, Turing machines, partial recursive functions, recursive and recursively enumerable sets)
(Key: correct, incorrect, partially correct.)
This is a draft. I am making edits on the wiki to be able to preview the quiz as I make it.
- Which of the following has a different meaning than the rest?
- Recursively enumerable set
- Semirecursive set
- Effectively enumerable set
- PARTIALLY. This is equivalent to most of the others. However, note that "effectively" is an informal notion so we are implicitly invoking the Church–Turing thesis.
- Computably enumerable set
- Turing-recognizable set
- Partially recursive set
- CORRECT. This option is unlike the others in a trivial sense: it's not even a term that is defined! This question is included here at the beginning because later in the quiz, we will be free to alternate between these equivalent terms.
- Which of the following has a different meaning than the rest?
- Recursive set
- Computable set
- Decidable set
- Effectively computable set
- PARTIALLY. This is equivalent to most of the others. However, note that "effectively" is an informal notion so we are implicitly invoking the Church–Turing thesis.
- Computably enumerable set
- Which of the following has a different meaning than the rest?
- Partial recursive function
- Partial μ-recursive function
- Computable total or partial function
- Recursive total or partial function
- General recursive total or partial function
- Turing-computable total or partial function
- Effectively calculable total or partial function
- PARTIALLY. This is equivalent to most of the others. However, note that "effectively" is an informal notion so we are implicitly invoking the Church–Turing thesis.
- Effectively computable total or partial function
- PARTIALLY. This is equivalent to most of the others. However, note that "effectively" is an informal notion so we are implicitly invoking the Church–Turing thesis.
- Primitive recursive function
- CORRECT. This is a weaker notion than the rest.
- Let S be a one-place semirecursive relation on N, and let us attempt to define a partial function f: N → N as follows: if S(n) then f(n) = 1, and if not S(n) then f(n) = 0. What is the strongest statement we can make about f?
- f is well-defined
- PARTIALLY. Indeed f is well-defined, but we can say something stronger.
- f is total
- CORRECT. f is total because exactly one of S(n) or ¬S(n) holds for each n ∈ N (law of excluded middle).
- f is recursive and total (f is a computable total function)
- INCORRECT. S is only semirecursive, so both S and ¬S may end up in an infinite loop.
- Let S be a subset of the natural numbers. Which of the following is not equivalent to saying that S is recursively enumerable?
- S is the domain of a computable partial function
- S can be enumerated in a computable manner as a₀, a₁, a₂, … in increasing order
- CORRECT. This is equivalent to saying S is recursive, and there exist recursively enumerable sets that are not recursive.
- S is the range of a computable partial function
- There exists a two-place recursive relation R on N such that x ∈ S iff ∃t R(x, t)
- S is empty or the range of a primitive recursive function
- Let f: N → N be a partial function. Which of the following is not equivalent to saying that f is computable?
- f is computable by a Turing machine
- f is definable from the basic functions (zero, successor, identity) using the processes of composition, primitive recursion, and minimization
- f is computable by a register machine (abacus machine)
- f is computable by a program that uses basic operations (clearing, increment, copy) and a bounded loop
- CORRECT. This is equivalent to saying f is primitive recursive, and there exist recursive functions that are not primitive recursive.
- What is the strongest statement we can make about the set of all real numbers?
- It is enumerable
- It is recursively enumerable
- It is recursive
- It is primitive recursive
- We cannot say any of the other options
- CORRECT. The weakest statement is enumerability, but R is uncountable so it cannot be enumerated.
- What is the strongest statement we can make about the set of even natural numbers?
- It is enumerable
- It is recursively enumerable
- It is recursive
- It is primitive recursive
- We cannot say any of the other options
- What is the strongest statement we can make about the set of all natural numbers?
- It is enumerable
- It is recursively enumerable
- It is recursive
- It is primitive recursive
- We cannot say any of the other options
- What is the strongest statement we can make about the set of all rational numbers?
- It is enumerable
- It is recursively enumerable
- It is recursive
- It is primitive recursive
- We cannot say any of the other options
- What is the strongest statement we can make about the set of all pairs (m, n) such that the mth Turing machine when started with input n halts?
- It is enumerable
- It is recursively enumerable
- It is recursive
- It is primitive recursive
- We cannot say any of the other options
- Can a characteristic function for a set of natural numbers be non-total?
- No; for every input natural number, a characteristic function must output 0 or 1 depending on whether the number is in the set or not. This means the characteristic function is always total.
- CORRECT. However, note that there are also positive semicharacteristic functions, which need not be total.
- Yes; for instance, the characteristic function of a semirecursive set is only defined for some inputs.
- The characteristic function of a semirecursive set is actually total. However, that characteristic function need not be computable.
- Which of the following operations are the semirecursive relations not closed under?
- Conjunction (logical AND)
- Disjunction (logical OR)
- Negation (logical NOT)
- Bounded universal quantification
- Bounded existential quantification
- Existential quantification (not necessarily bounded)
- INCORRECT. A semirecursive relation already can be written in the form ∃t R(x, t) for some recursive relation R. Intuitively, adding on more existential quantifiers at the beginning doesn't change the "kind" of relation. More carefully, if we have S(x, y) iff ∃t R(x, y, t) for some recursive relation R, then we can write the relation ∃y S(x,&nbps;y) as ∃M ∃y<M ∃t<M R(x, y, t), where ∃y<M ∃t<M R(x, y, t) is recursive (as it only uses bounded quantification). In other words, we can combine the two unbounded existential quantifiers into a single unbounded "upper bound" and use bounded existential quantifiers for the rest.
- What information does a single instruction in a Turing machine use? (Alternatively, what are the inputs to the transition function of a Turing machine?)
- A symbol
- A symbol and a state
- A symbol and an action
- A symbol, a state, and an action
- A symbol, two states, and an action
- INCORRECT. This is what a full instruction looks like, but only the symbol and one of the states are used; the other state and the action are the outputs of the transition function.
- Which of the following is an incorrect explanation of why there is a countable number of Turing-computable functions?
- We can encode each Turing machine by a list of quadruples (in-state, scanned symbol, output action, out-state)
- INCORRECT. This is the most direct way to show that there are a countable number of Turing-computable functions.
- Turing machines are basically computer programs, whose source code can be written as finite strings of a finite alphabet; therefore, there are a countable number of them
- PARTIALLY. This explanation works, but it sort of appeals to the Church–Turing thesis.
- Turing-computable functions are equivalent to partial recursive functions, and there are a countable number of partial recursive functions.
- PARTIALLY. While this is not wrong, the equivalence of Turing computability and recursiveness is sort of a more advanced fact (also, does the proof the equivalence use countability anywhere?).
- A Turing machine comes with an infinitely long tape which is countable. At any stage during the computation, only finitely many squares on the tape have a symbol written on them. Therefore, there are a countable number of Turing machines.
- CORRECT. This explains why the configuration of a stage of computation is finite, but doesn't explain why there are countably many Turing machines.
- Let f: N → N be a computable partial function. What can we say about the graph relation G of f, defined by G(x, y) iff f(x) = y?
- G is partial recursive
- G is recursive
- G is semirecursive
- Nothing; we cannot in general conclude anything about G
- Let f: N → N be a partial function. Suppose the graph relation G of f, defined by G(x, y) iff f(x) = y, is a semirecursive relation. What can we say about f?
- f is primitive recursive
- f is partial recursive
- f is recursive and total
- f is semirecursive
- INCORRECT. It does not make sense to ask whether a partial function is semirecursive (we can only ask this for relations and sets).
- Nothing; we cannot in general conclude anything about G
- If f: Nk → N is a k-place partial recursive function, then the result of applying the minimization operator (also called the μ operator) to f is
- A (k − 1)-place partial recursive function
- A k-place partial recursive function
- A (k + 1)-place partial recursive function
- A subset of Nk − 1
- A subset of Nk
- A subset of Nk + 1
- A natural number
Score:
.
Quiz-9
|
Tip: To turn text into a link, highlight the text, then click on a page or file from the list above.
|
|
|
|
|
Comments (0)
You don't have permission to comment on this page.