PDF of Prof. Santosh’s handwritten notes are here.

**What is computation?**

We think of computation as being by a device such as calculator, phone, laptop, etc…something that actually computes something. However, we could also view computation from a different perspective. In fact, we can look at the universe as a giant computational device, where the laws of nature takes some input (the current state of the universe) and produce an output (the universe at a future state). For a more concrete example, we could consider the weather on Earth to be a computational device, which produces the current temperature in a specific location.

Nearly anything could be formulated as a computational device. To help in our study of what is computable, we will formulate a couple simple, well-defined computational devices: a finite state machine and a Turing machine.

**Finite state machine (automaton)**

- , finite set of possible states
- , alphabet, which we assume includes a “blank” symbol
- , a transition function
- , accept state
- , reject state
- , start state

The above set of rules can develop systems that will recognize certain languages. For example, we could design a finite state machine that determines whether a string is in the language .

**Question: What is the set of languages recognized by finite state machines?**

Is it all languages? How do we rule out that language is not computable by a finite state machine? If something is not computable by a finite state machine, is it not computable by any device?

More concretely, can we construct a finite state machine to recognize the language ? We can easily write a program on a modern computer to recognize this language: just count the number of zeros, then count the number of ones, and check if they’re equal. But for a finite state machine, we don’t have the luxury of a counter. In fact, it turns out that no finite state machine can recognize this language.

**Turing Machine**

We now consider a more powerful model of computation, known as a Turing Machine (TM), which is essentially a finite state machine where we additionally get access to a read/write tape where we can store information.

- , set of states
- , input alphabet (does not include a blank character)
- , tape alphabet (includes a blank character and all of )
- read/write tape, which we assume to have infinite length
- , transition function.

It is clear that a TM can compute things that finite state machines cannot by considering our previous example: . But what all can a TM compute?

**Church-Turing thesis:** Anything computable can be computed by a TM.

Suppose a TM accepts a set of strings, i.e., a language . Now, we know that

- the set of languages is uncountable
- the set of TM’s is countable
- description of a TM, , which can be encoded as a single string. Recall the set of finite strings over a finite alphabet is countable.

Therefore, not all languages can be recognized by a TM.

**Question: **What is a language that cannot be decided by a TM?

Consider .

**Theorem 1.** There does not exist a TM such that

- accepts if
- does not accept if

**Proof: **Suppose, for a contradiction, that such an exists. Define a TM on input as follows:

- Run on .
- accepts if rejects.
- rejects if accepts.

Now, does accept ? From the definition of ,

- accepts if rejects
- rejects if accepts

Therefore, we have a contradiction and must conclude that TM cannot possibly exist.

**Theorem 2. **Define

. The language is undecidable.

**Proof: **Suppose there exists a TM that decides . Then, we can decide with the following TM:

- Run on .
- If says does not halt, then reject.
- Else run on ; accept if accepts and reject if rejects.

by simply running the TM on the inputs which halt. This contradicts Theorem 1.

We also have the following similar theorems about undecidability.

**Theorem 3.** Determining whether two TM’s accept the same language is undecidable.

**Theorem 4. **Determining if a TM accepts *any* string is undecidable.

**Proof: **Suppose there exists a TM that decides the language .

Define a TM on input :

- if , reject
- if , then run on

Now define a TM on input :

- Run on the TM
- Reject if accepts, and accept if rejects

Then,

- accepts if , which implies that does not accept
- rejects if and thus accepts

Thus we have decided if accepts , contradicting Theorem 1.