Complexity And Computability

Front 1

What are the differences between a Turing machine and a finite automata?

Back 1

1) A Turing machine can both write onthe tape and read from it.
2) The read-write head can move bothh to the left and to the right.
3) The tape is infinite.
4) The special states for rejecting and accepting take immediate effect.

Front 2

What do Turing machines fundamentally do? That is, given a Turing machine M and a word w, what does a Turing machine do with w?

Back 2

Fundamentally, all Turing machines accept a Language L that is defined by the Turing machine as all input strings that the Turing machine accepts. The Turing machine and the Language are therefore in fact equivilant. A Turing machine is needed to know though whether a word w is in the Language. Therefore a Turing machine can be thought of as a Language + a way to know if strings are members of that Language.

Front 3

What is the Formal Definition of a Turing Machine

Back 3

A Turing machine is a 7-tuple, (Q, Alpha, TapeAlpha, Transition, Q0, QAccept, QReject)
1)Q is the set of states
2)Alpha is the input alphabet not containing the special blank symbol.
3)TapeAlpha is the tape alphabet, where the special blank symbol is an element of TapeAlpha and where the Tape Alphabet is a superSet of Alpha.
4)Transition functions of the form Q X Alpha -> Q X TapeAlpha X {L,R}
5) Q0 is the start state, a subset of Q
6)QAccept is the accepting state, a subset of Q.
7)QReject is the rejecting state, a subset of Q.

Front 4

Call a Language Turing-recognizable if ...

Back 4

... some Turing machine recognizes it. Three outcomes are possible, the machine will either end in the accept state, the reject state, or will loop.

Front 5

Call a Language Turing-decidable (or simply decidable) if ...

Back 5

... some Turing machine decides it. Only two outcomes are possible on a Turing decidable Language, the Turing machine that decides it will either accept or reject.

Front 6

What is an enumerator?

Back 6

An enumerator is a variant of a Turing machine that has an attached printer. The language enumerated by a enumerator E is the collection of all strings that it eventually prints out. The strings may be in any order, and repetition may be allowed.

Front 7

Proof: A language L is Turing recognizable iff some enumerator enumerates it.

Back 7

First, if E enumerates L, then a TM M recognizes L. M works in this way.
M = "On input w:
1.Run E. Every Time that E outputs a string, compare it wih w.
2.If w ever appears on the output of E, accept."

Now for the other direction. If TM M recognizes a language L, we can construct the following enumerator E for L. Say that S1, S2, S2, ... is a list of all possible strings in Alpha*.
E="Ignore the input.
1.Repeat the following for i=1,2,3,...
2.Run M for i steps on each input, S1, S2, ..., Si.
3.If any computations accept, print out the corresponding Sj"
So, if M accepts a particular string s, eventually it will appear on the list generated by E. In fact, it will appear on the list infinitely many times because M runs from the beginning on each string for each repetition of step 1. This procedure gives the effect of running M in parallel on all possible input strings.

Front 8

Hilberts Problem

Back 8

In 1900, mathematician David Hilbert delivered a now-famous address to the International Congress of Mathematicians in Paris. In his lecture, he identified 23 mathematical problems and possed them as challenges for the comming century. The 10th problem on the list concerned algorithms. The challenge was to devise an algorithm that determined if a given polynomial had a integral root. Clearly, no such algorithm exist, but this could not have been proven at the time as the definition of an algorithm had not been formalized yet.

Front 9

Church-Turing thesis

Back 9

A 1936 paper by Alonzo Church and Allan Turing formally defined the notion of an algorithm. Church defined algorithms using a system known as his lambda calculus. Turing defined algorithms using his machines. The two definitions were shown to be equivilant.

Front 10

What is the notation for encoding an Object?

Back 10

<O> means that O was encoded into a single string, it does not matter how it was encoded, as a Turing machine exist that can convert one string into another string. By this notation <O1,O2,O3,O4,O5> converts all 5 of these objects into a single string.

Front 11

What are subroutines in turing machines?

Back 11

Subroutines in Turing machines are also Turing machines. Ususally the calling subroutine does some sort of filtering on the input and then calls the subroutine. It then receives the accept or reject state from the contained Turing machine and then accepts or rejects that.

Front 12

What is Adfa, Arex?

Back 12

Adfa means that a DFA accepts string w. Arex means that a regular expression accepts a string w. These are easily proved using Turing machines. Both of these Languages are decidable.

Front 13

What is Edfa,

Back 13

Edfa test whether a DFA accepts any string at all. That is, are there any strings w that the DFA will end on the accept state. Edfa is decidable.
Edfa = {<A>| A is a DFA and L(A) = "empty set"}

Front 14

What is EQdfa

Back 14

EQdfa test whether two DFA's recognize the same language.
EQdfa = {<A,B>|A and B are DFA's and L(A) = L(B)}
It is a decidable Language. It is proven using the symmetric difference.

Front 15

What is Atm? Is it decidable?

Back 15

Atm is the question of testing whether a Turing machine accepts a given input string. We call it Atm by analogy with Adfa and Acfg. But, whereas Adfa and ACFG were decidable, Atm is not. Let
Atm = {<M,w>|M is a TM and M accepts w}

Front 16

Proof: Atm is undecidable.

Back 16

First, observer that ATM is Turing recognizable. The following Turing machine U recognizes all Atm.
U="On input <M,w>, where M is a Turing machine and w is a string:
1. Simulate M on input w
2. If M ever enters its accept state, accept; If M ever enters its reject state, reject." Note that this Machine may loop on input <M,w> which is why it is not a decider.

Front 17

Diagonalization Method

Back 17

Invented by George Cantor in 1873. Cantor was concerned with measuring the size of infinite sets.Clearly, you cannot use the counting method that you would use with finite sets, so something else must be used.
However, he did notice that two sets have the same size if each element of one set can be mapped to one other element of another set. This allows comparisons of the sets without resorting to counting.

Front 18

One-to-One functions

Back 18

If we have two sets A and B, a function is one-to-one if it never maps two different elements to the same place, that is f(c) != f(d) whenever c != d.

Front 19

Onto functions

Back 19

If we have two sets A and B, a function is onto if it hits every element of B. That is, for every b that is an element of B, there is an a that is an element of A, such that f(a) = b.

Front 20

Correspondence

Back 20

A function that is both one to one and onto is called a correspondence. If there is a correspondence between two sets, we say the two sets are the same size.

Front 21

R is uncountable

Back 21

In order to show that R is uncountable, we show that no correspondence exist between N and R. The proof is by contradiction.

Build something like this
n | f(n)
----------
1 | 3.14159
2 | 55.5555
3 | 0.12345
4 | 0.50000
...| ...

Now we need to show that their is a number that exist that is not a number from any number liste by the function. In order to do so, we construct a number that is different at the nth decimal digit than the f(n) value of n. This number does not exist in the listing, yet it is valid, so there must be numbers (infinitly many) that are not mappable to the Natural numbers n. Therefore our original implied assumption of the reals being countable is wrong, and R is in fact uncountable.

Front 22

Some Languages are not Turing-recognizable.

Back 22

First, we show that the set of all Turing machines are countable. Notice that the set of all strings in an alphabet alpha is countable. Any Turing machine can be "serialized" into a string, therefore the turing machines are countable.

To show that all Languages are uncountable requires a little more thought. First observe that the set of infinite binary sequences is uncountable. An infinite binary sequence is an unending sequence of 0's and 1's. Diagonalization will demonstrate the uncountability of the unending binary sequence. Let B be the set of all undending binary sequences. Now let A be the set of all languages over alphabet Alpha. Let Alpha* = {s1, s2, s3, ...}. Each Language L that is an element of A has a unique sequence of 0's and 1's (1 if word is in, 0 if not) called the characteristic sequence of L. The function A -> B, where f(A) equals the characteristic sequence of L is one-to-one and onto, and hence a correspondence. Therefore as B is uncountable, A is uncountable as well.

Front 23

The halting problem is undecidable. What is the halting problem?

Back 23

Now we are ready to prove the undecidability of the language
Atm = {<M,w>|M is a TM and M accepts w}

Proof: we assume that Atm is decidable and obtain a contradiction.
Suppose we have the following machine
H(<M,w>)= {
accept if M accepts w
reject if M does not accept w
}

Now we construct a new machine D with H as a subroutine.
D = "On input <M>, where M is a TM:
1. Run H on input <M,<M>>
2. Output the opposite of what H outputs. That is, if H accepts, reject and if H rejects, accept."

No matter what D does, it is forced to do the opposite, which is obvously a contradiction. Thus neither TM D nor TM H can exist. In terms of diagonalization, the contradiction occurs where the new diagonal entry must be the opposite of itself.

Front 24

A language is decidable iff it is both ...

Proof:

Back 24

A language is decidable iff it is both Turing-recognizable and coTuring-recognizable.

Proof:
First, if A is decidable, we can easily see that both A and its the complement of A are Turing recognizable. Any decidable language is Turing-recognizable, and the complement of a decidable language also is decidable.
For the other direction, if both A and Acomplement are Turing-recognizable, we let M1 be the recongizer for A and M2 be the recongizer for Acomp. The following Turing machine M is a decider for A.
M="On input w:
1. Run both M1 and M2 on input w in parralel.
2. If M1 accepts , accept; if M2 accepts , reject."
Because M always halts and accepts, it is a decider, so A is decidable.

Front 25

Proof: the complement of Atm is not Turing-recognizable.

Back 25

We know that Atm is Turing-recongizable. If the complement of Atm also were Turing recognizable, Atm would be decidable. Atm has been proven to not be decidable though, so the complement of Atm must not be Turing-recognizable.