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.
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?
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
- accepts if , which implies that does not accept
- rejects if and thus accepts
Thus we have decided if accepts , contradicting Theorem 1.