Be encoded by a finite binary string #M. Moreover, our ...

Church-Turing Thesis: Every function f: {0,1}* -> {0,1}* which is "effectively computable" is computable by a Turing Machine.

Observation: Every Turing Machine (equivalently, every python program, or evey program in your favorite language) M can be encoded by a finite binary string #M. Moreover, our encoding guarantees #M != #M' whenever M and M' are different Turing Machines (different programs). Recall: Every finite binary string can be thought of as a natural number written in binary, and vice versa.

Therefore, we can think of #M as a natural number. E.g. If #M = 1057, then we are talking about the 1057th Turing Machine, or 1057th python program. Intuitive takeaway: At most, there are as many different Turing Machines (Programs) as there are natural numbers.

We will now show that some (in fact most) decision problems f:{0,1}* -> {0,1} are not computable by a TM (python program). -- If decision problem f is not computable by a TM/program then we say it is "undecidable".

Theorem: There are functions from {0,1}* to {0,1} which are not computable by a Turing Machine. (We say, undecidable). Corollary: Assuming the CT thesis, there are functions which are not "effectively computable".

Proof of Theorem: - Recall that we can think of instead of {0,1}*. - "How many" functions f : -> {0,1} are there? - We can think of each such function f as an infinite binary string.

- For each x in (0,1), we can write its binary expansion as an infinite binary string like this

- The string to the right of the decimal point can be interpreted as a function f_x from natural numbers to {0,1} - f_x(i) = ith bit of x to the right of the decimal point. - In other words: For each x in (0,1) we get a different function f from natural numbers to {0,1}, so there are at least as many decision problems as there are numbers in (0,1).

- How many different Turing Machines (python programs) are there? -- Recall: each Turing Machine (python program), can be encoded as a finite string. Also, finite binary strings are in a bijection with the natural numbers. - At most, there are as many Turing Machines (python programs) as there are natural numbers. -- We say: Turing Machines are "countable".

- Suppose for a contradiction that each decision problem can be solved by a TM (or, python program).

- We have an injective map from (0,1) to

I.e., (0,1) are countable.

Theorem (Cantor): (0,1) are uncountable. (There does not exist an injection from (0,1) to the natural numbers). Note: Often this theorem is stated as the real numbers are uncountable, because it turns out that

We derived a contradiction.

To summarize: There are as many algorithms as there are whole numbers. But there are as many decision problems as there are real numbers. We know form Cantor's theorem that there are way more real numbers than whole numbers, so there are way more problems then algorithms.

Recall: Turing Machines == Python programs === C programs === algorithms in your favorite language.

- Historically, we used to think of each algorithm as a different "machine". In other words, algorithms were thought of as "hardware", while their inputs/outputs/intermediate results were thought of as the software.

- One of Turing's great insights, which is obvious to us now but was revolutionary at the time, is that you can think of algorithms are "software" -- Each Turing Machine / Algorithm in your favorite language can be written as a finite binary string -- There exists a "universal Turing Machine" / "Interpreter in your favorite language" which can take another TM / algorithm as input and "simulate it".

Definition: A Universal Turing Machine U is a Turing Machine which takes as input a string #M describing a Turing Machine M, and another string x, and "simulates" M on x.

Nowadays we call U an interpreter (software perspective), or a general purpose computer (hardware perspective).

Theorem (Turing): A universal Turing Machine exists. Great insight at the time, and the proof was tricky.

Interpretation of this theorem in modern lingo: -- Interpreters exist (Software perspective) -- General purpose computers exist (Hardware perspective). ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download