Computability

Summarized notes from Introduction to Theory of Computation, Chapters 4-5

Church-Turing Thesis

Function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine.

Rice's Theorem

Determining any non-trivial semantic property of the languages recognized by Turing machines is undecidable.

Computable functions

A function $f:{\mathrm{\Sigma }}^{\ast }⟶{\mathrm{\Sigma }}^{\ast }$ is a computable function if some Turing machine $M$, on every input $w$, halts with just $f(w)$ on its tape.

Decidability

• reasons why decidability matters:

  • undecidable problem must be simplified or altered before it can be solved
  • it is important to have this perspective on computation in general

• some decidable problems for regular languages:

  • acceptance problem: whether FA accepts a given string
  • emptiness testing: whether or not FA accepts any string
  • determining if two DFAs accept the same language

• some decidable problems from context-free languages:

  • acceptance problem: determining if CFG generates a specific string
  • emptiness testing: whether CFG generates any string at all
  • every context-free language is decidable by TM

• some undecidable problems:

  • whether a TM accepts an input string
  • determining whether TM recognizes a regular language
  • halting problem: TM halts on given input
  • determining if CFG generates all possible strings
  • port correspondence problem

Reducibility

Reduction is a way of converting one problem to another problem such that a solution to the second problem can be used to solve the first one.

Reducing problems to others often helps to prove some problem is undecidable.

Computation history method

• technique for proving that TM is reducible to certain language

• often useful when proving undecidability involves testing for existence of something

• for TM, computation history is the sequence of configurations the machine goes through

  • accepting computation history, for $M$ on $w$, is a sequence of configurations, $C_1,C_2,\dots ,C_l$ where $C_1$ is the start configuration for $M$ on $w$, each $C_i$ follows from $C_{i-1}$ according to the rules of $M$, and $C_l$ is accepting configuration
  • rejecting computation history is defined similarly except $C_l$ is a rejecting configuration

• computation histories are finite sequences => if $M$ does not halt, neither accepting or rejecting history exists

• deterministic machines have at most 1 computation history on any given input, nondeterministic can have multiple

Mapping reducibility

Also called many-one reducibility,

Language A is mapping reducible to language B, written $A{\le }_{m}B$, if there is a computable function $f:{\mathrm{\Sigma }}^{\ast }⟶{\mathrm{\Sigma }}^{\ast }$, where for every $w$,

$$w\in A\iff f(w)\in B.$$

The function $f$ is called the reduction from A to B.

• mapping reduction of A to B provides a way to convert questions about membership testing in A to membership testing in B, e.g.
  • if $A{\le }_{m}B$ and B is decidable, then A is decidable
  • if $A{\le }_{m}B$ and B is Turing-recognizable, then A is Turing-recognizable
  • if $A{\le }_{m}B$ and A is undecidable, then B is undecidable
  • if $A{\le }_{m}B$ and A is not Turing-recognizable, then B is not Turing-recognizable
• if one problem is mapping reducible to another previously solved problem, the original problem can be solved

Turing reducibility

A generalization of mapping reducibility:

Language A is turing reducible to language B, $A{\le }_{T}B$, if A is decidable relative to B.