5.1 UNDECIDABLE PROBLEMS FROM LANGUAGE THEORY

Question 1

The halting problem

Answer 1

The problem of determining whether a Turing machine halts (by accepting or rejecting) on a given input

Question 2

Mapping reducibility

Answer 2

Roughly speaking, being able to reduce problem A to problem B by using a mapping reducibility means that a computable function exists that converts instances of problem A to instances of problem B.

Question 3

Language A is mapping reducible to language B, written A ≤m B,
if

Answer 3

here is a computable function f : Σ∗−→Σ∗, where for every w, w ∈ A ⇐⇒ f ( w ) ∈ B .
The function f is called the reduction from A to B.