鵝
歷
☌
←
→
⇡
04 Nov 2015

Automata, Computability, and Complexity Or, Great Ideas in Theoretical Computer Science

[course site for ‘Automata, Computability, and Complexity’] [lecture notes]

3 Deterministic finite automata (DFAs) and nondeterministic finite automata (NFAs)

A FA M accepts a word w if w causes M to follow a path from the start state to an accept state.

The set of FA-recognizable languages is closed under all six operations (union, intersection, complement, set difference, concatenation, star).

4 NFAs and regular expressions

(Informally) How NFAs compute
  • Follow allowed arrows in any possible way, while “consuming” the designated input symbols.
  • Optionally follow any ε arrow at any time, without consuming any input.
  • Accepts a string if some allowed sequence of transitions on that string leads to an accepting state.
String w is accepted if
δ*( q0, w ) ∩ F ≠ ∅ , that is, at least one of the possible end state is accepting.
L(M)
the language recognized by NFA M, = { w | w is accepted by M}.

NFV vs DFA

Theorem: NFAs and DFAs have the same power.

But sometimes NFAs are simpler than equivalent DFAs.

(NFA) simpler
has the power to “guess” when to start matching
Regular operations
Union, concatenation, and star
An algebraic-expression notation for describing (some) languages, rather than a machine representation.

FA-recognizable (regular) languages are closed under set operations, concatenation, and star.

The languages denoted by regular expressions are exactly the regular (FA-recognizable) languages.

6 Turing machines

Universal Turing Machines
In his 1936 paper “On Computable Numbers” (in some sense, the founding document of computer science)
Turing proved that we can build a Turing machine U that acts as an interpreter for other Turing machines.
In other words, U’s input tape can contain a description of another Turing machine, which is then simulated step by step.

If a universal machine didn’t exist, then in general we would need to build new hardware every time we wanted to solve a new problem: there wouldn’t even be the concept of software. This is why Professor Aaronson refers to Turing’s universality result as the “existence of the software industry lemma”!

They can thus emulate a machine with any number of states, but themselves requiring only a few states…

6.4 The Church-Turing Thesis

Related to the idea of universal machines is the so-called Church-Turing thesis, which claims that anything we would naturally regard as “computable” is actually computable by a Turing machine. Intuitively, given any “reasonable” model of computation you like (RAM machines, cellular automata, etc.), you can write compilers and interpreters that translate programs back and forth between that model and the Turing machine model. It’s never been completely clear how to interpret this thesis: is it a claim about the laws of physics? about human reasoning powers? about the computers that we actually build? about math or philosophy?

But as we’ll see, even Turing machines have their limitations.

6.5 Halting is a problem

Suppose we have a Turing machine that never halts. Can we make a Turing machine that can detect this? In other words, can we make an infinite loop detector? This is called the Halting problem.

The benefits of such a machine would be widespread. For example, we could then prove or disprove Goldbach’s Conjecture, which says that all even numbers 4 or greater are the sum of two primes. We could do this by writing a machine that iterated over all even numbers to test this conjecture:

for i = 2 to infinity:
if 2*i is not a sum of two primes
then HALT

It turns out that such an infinite loop detector can’t exist. This was also proved in Turing’s paper, by an amazingly simple proof that’s now part of the intellectual heritage of computer science.

We argue by contradiction. Let P be a Turing machine that solves the halting problem. In other words, given an input machine M, P(M) accepts if M(0) halts, and rejects if M(0) instead runs forever. Here P(M) means P run with an encoding of M on its input tape, and M(0) means M run with all 0’s on its input tape. Then we can easily modify P to produce a new Turing machine Q, such that Q(M) runs forever if M(M) halts, or halts if M(M) runs forever. Then the question becomes: what happens with Q(Q)? If Q(Q) halts, then Q(Q) runs forever, and if Q(Q) runs forever, then Q(Q) halts…

6.6 There are multiple infinities

In the 1880’s, Georg Cantor discovered the extraordinary fact that there are different degrees of infinity. In particular, the infinity of real numbers is greater than the infinity of integers

6.7 Infinitely many unsolvable problems

We can use the existence of these multiple infinities to prove that there are uncomputable problems. We’ll begin by showing that the number of possible Turing machines is the smallest infinity, the infinity of integers.

Define a Turing machine as a set of states and a set of transitions from each state to another state (where the transitions are based on the symbol being read). A crucial aspect of this definition is that both sets are finite. Because of this, the number of Turing machines is countable

The number of problems, on the other hand, is a greater infinity: namely, the infinity of real numbers. This is because we can define a problem as a function that maps every input x ∈ 0, 1∗ to an output (0 or 1).

7 Decidability

original slide

TM M recognizes language L
provided that L = { w | M on w reaches qacc } = { w | M accepts w }.
TM M decides language L
provided that both of the following hold:
  • On every w, M eventually reaches either qacc or qrej.
  • L = { w | M on w reaches qacc }.
Theorem 4 (A basic connection between Turing-recognizable and Turing-decidable languages)
L is Turing decidable if and only if L and Lc are both Turing-recognizable.

Language Classification

Cardinality argument

Closure Properties

Recursively Enumerable Languages

Theorem 8 (connection between recursive enumerability and Turing recognizability)
L is recursively enumerable if and only if L is Turing-recognizable.

Turing Machines that solve graph problems

the problem of whether a given graph has a cycle of length > 2.

all the other decision problems we considered for DFAs, NFAs, and regular expressions are Turing-decidable (not just Turing-recognizable).

Undecidability of the Turing Machine Acceptance Problem