CHAPTER 4,5 DEFINITIONS

Question 1

What is the definition of undecidability?

Answer 1

A problem is undecidable if there is no Turing machine that can solve it (i.e., decide “yes” or “no” for every input).

Question 2

What does NSA stand for in the context of Turing machines?

Answer 2

NSA (Non-Self-Acceptance Problem) is the problem of determining whether a Turing machine does not accept its own encoding.

Question 3

Define the NSA problem.

Answer 3

Given a Turing machine ( M ), NSA is defined as:
( ext{NSA}(M) := egin{cases} 1 & ext{if } M(M)
eq 1; \ 0 & ext{otherwise.} end{cases})

Question 4

What does SA stand for in the context of Turing machines?

Answer 4

SA (Self-Acceptance Problem) is the problem of determining whether a Turing machine accepts its own encoding.

Question 5

Define the SA problem.

Answer 5

Given a Turing machine ( M ), SA is defined as:
( ext{SA}(M) := egin{cases} 1 & ext{if } M(M) = 1; \ 0 & ext{otherwise.} end{cases})

Question 6

Define the ACCEPT problem.

Answer 6

Given a Turing machine ( M ) and input ( x ), ACCEPT is defined as:
( ext{ACCEPT}(M, x) := egin{cases} 1 & ext{if } M(x) = 1; \ 0 & ext{otherwise.} end{cases})

Question 7

What is the definition of the HALT problem?

Answer 7

Given a Turing machine ( M ) and input ( x ), HALT is defined as:
( ext{HALT}(M, x) := egin{cases} 1 & ext{if } M(x)
eq infty; \ 0 & ext{otherwise.} end{cases})

Question 8

Define the HALT-EMPTY problem.

Answer 8

Given a Turing machine ( M ), HALT-EMPTY is defined as:
( ext{HALT-EMPTY}(M) := egin{cases} 1 & ext{if } M(epsilon)
eq infty; \ 0 & ext{otherwise.} end{cases})

Question 9

What is Rice’s Theorem?

Answer 9

Rice’s Theorem states that a language ( L ) of Turing machine encodings is undecidable if:
* ( L
eq emptyset )
* ( L
eq Sigma^* )
* If ( M ) and ( M’ ) are accept-equivalent, then either both are in ( L ) or both are not.

Question 10

What defines a first-order language vocabulary?

Answer 10

A vocabulary ( Omega ) consists of:
* Constant symbols (( Con_Omega ))
* Function symbols (( Fun_Omega )), each with an arity
* Predicate symbols (( Pred_Omega )), each with an arity.

Question 11

What is the definition of first-order formula validity?

Answer 11

A first-order formula ( varphi ) is valid (( models varphi )) if it is true in every model under every assignment.

Question 12

What is the definition of first-order formula satisfiability?

Answer 12

A first-order formula ( varphi ) is satisfiable if it is true in some model under some assignment.

Question 13

What theorem explains the existence of undecidable problems?

Answer 13

There exist undecidable problems because the set of all languages is uncountable, while the set of Turing machines is countable.

Question 14

Is the NSA problem undecidable?

Answer 14

True. The NSA problem is undecidable.

Question 15

Is the SA problem undecidable?

Answer 15

True. The SA problem is undecidable.

Question 16

Is the ACCEPT problem undecidable?

Answer 16

True. The ACCEPT problem is undecidable.

Question 17

Is the HALT problem undecidable?

Answer 17

True. The HALT problem is undecidable.

Question 18

Is the HALT-EMPTY problem undecidable?

Answer 18

True. The HALT-EMPTY problem is undecidable.

Question 19

What does Church’s Theorem state?

Answer 19

The problem of determining whether a first-order formula is valid (FO-VAL) is undecidable.

Question 20

Is first-order satisfiability undecidable?

Answer 20

True. The problem of determining whether a first-order formula is satisfiable (FO-SAT) is undecidable.

Question 21

Is first-order logical consequence undecidable?

Answer 21

True. The problem of determining whether ( Gamma models varphi ) (FO-CONS) is undecidable.