Skip to content

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: \Sigma^* \longrightarrow \Sigma^*\) 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 \leq_m B\), if there is a computable function \(f: \Sigma^* \longrightarrow \Sigma^*\), where for every \(w\),

\[ w \in A \Leftrightarrow 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 \leq_m B\) and B is decidable, then A is decidable
    • if \(A \leq_m B\) and B is Turing-recognizable, then A is Turing-recognizable
    • if \(A \leq_m B\) and A is undecidable, then B is undecidable
    • if \(A \leq_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 \leq_T B\), if A is decidable relative to B.