FLA CHAPTER 2,3 DEFINITIONS Flashcards
(29 cards)
What is an alphabet?
An alphabet is a finite, non-empty set whose elements are called symbols.
Definition 2.2.1
Define a word in an alphabet Σ.
A word in an alphabet Σ is a finite sequence of symbols from Σ.
Definition 2.2.3
What denotes the length of a word w?
|w| denotes the length of a word w.
Definition 2.2.3
What does Σ* represent?
Σ* denotes the set of all words in Σ.
Definition 2.2.3
What is the empty word denoted by?
The empty word is denoted by ε.
Definition 2.2.3
Define a computational problem.
A computational problem is a function from {0,1}* to {0,1}*.
Definition 2.3.1
What is a decision problem?
A decision problem is a function from {0,1}* to {0,1}.
Definition 2.3.4
What is a language over an alphabet Σ?
A language over an alphabet Σ is a subset of Σ*.
Definition 2.4.1
What does every word represent according to Principle 2.2.7?
Every word is a representation of some object.
Principle 2.2.7
True or False: Unary alphabets are suitable for all purposes.
False.
Remark 2.2.5
Can the focus be restricted to decision problems without loss of generality?
Yes.
Remark 2.3.8
Define a Turing machine.
A tuple M = ⟨Q, Γ, Δ, q_init, q_accept, q_reject, δ⟩ where Q is a finite set of states, Γ is the input alphabet, Δ is the tape alphabet, and δ is the transition function.
Definition 3.2.1
What is a configuration in a Turing machine?
A configuration is a word in Δ ∪ Q containing exactly one symbol from Q.
Definition 3.2.2
What is the initial configuration of a Turing machine M on input x?
The initial configuration is q_init x.
Definition 3.2.3
What does w ⊢ v signify?
It signifies that configuration w transitions to v. w yields v
Definition 3.2.4
Define computation in the context of Turing machines.
A computation is a sequence of configurations following the yields relation.
Definition 3.2.5
What does it mean for a Turing machine M to accept x?
M accepts x if the computation contains an accepting configuration.
Definition 3.2.6
What is a decider in the context of Turing machines?
A decider is a Turing machine that halts on every input.
Definition 3.2.9
What does it mean for a decision problem to be solvable?
A decision problem is solvable if M(x) = f(x) for all x ∈ Γ*.
Definition 3.2.12
What is the definition of decidability?
A decision problem is decidable if solvable by some Turing machine.
Definition 3.2.20
What is a computable function in relation to Turing machines?
A computable function f: Σ* → Σ* is computed if M(x) = f(x) for all x ∈ Σ*.
Definition 3.3.3
What is the time function t_M(n)?
Maximum number of steps it takes M to run on input of length n:
t_M(n) := max{|C(M,x)| : x ∈ Γⁿ}.
Definition 3.4.3
Define the space function S_M(n).
Total number of cells a TM M visits during its computation:
S_M(n) := max{S(M,x) : x ∈ Γⁿ}.
Definition 3.4.11
What is a Universal Turing Machine?
A Universal Turing Machine U(⟨M, x⟩) = M(x) for every M and x.
Definition 3.9.1
