Module 7
Theory

Theoretical Computer Science

€ The physical machine is important only insofar as it may be used to run
programs.

€ Look at a program is as a black box:

A program defines a matching from the set of all possible binary
(input) strings to some members of the set of all possible binary
(output) strings.

Given any input string, a program can do one of two things:

(1) Run for a while and halt, having produced an output matching,
or

(2) Produce output forever, thus matching the input to no finite
output string.

A Program as a Function on Binary Strings

Every string on the left has an arrow from it.

Every string on the right might not have an arrow to it.

Some of the arrows may point to nothing at all.

€ Another way to look at computation is to model what goes on "inside" the
black box.

€ A very simple model is the Turing Machine.

€ A Turing Machine (TM, for short) consists of:

(1) A tape of unlimited length, consisting of discrete cells.

(2) A finite control, which can read and write on the tape using a
tape head. The finite control has a fixed number of internal
states and at any time is in one and only one state.

The Turing Machine

€ Based on the symbol being read and the current state, a move of the TM
consists of

(1) Overwriting the current symbol

(2) Moving the read/write head one cell to the left or to the right
on the tape

(3) Changing the state of the finite control

Example: A simple TM that changes the leftmost run of zeros to ones and
then stops:

Present Present New New
State Symbol Write Move State

1 1 1 R 1
1 0 1 R 2
2 0 1 R 2

On initial input tape 1001, this TM would act as follows:

€ We can make a "clear box" definition of computation:

When we talk about programs, it is sufficient to talk about Turing
Machines, since everything you can do with a computer you can do with a
TM.

The "optimistic clear box" definition, also known as the Church-Turing
Thesis states:

Any reasonable definition of computation is equivalent to Turing
Machine-computable.

This can't be proven.

€ You can look at the Church-Turing Thesis as a confident challenge.

Encoding TMs

€ We can assign to each TM a unique serial number.

€ First, we encode each rule:

Every TM rule says, "In state i, reading j, write k,move in the
direction l, and change the state to m."

(1) Encode the state in unary, so that state i is represented by i
zeros.

(2) Encode the tape alphabet, so that, for instance, '0' --> 0, '1' -->
00, blank --> 000

(3) Encode left as 0, and right as 00

Separate the components of the 5-tuple by 1, so that the rule (1, 1, 1,
R, 1) is coded as

0 1 00 1 00 1 00 1 0

€ Now code all moves and separate each move by 11.

€ Finally, append 111 to the start and end of the TM code.

Example: The sample TM, with move descriptions

(1, 1, 1, R, 1)
(1, 0, 1, R, 2)
(2, 0, 1, R, 2)

would be coded as the string

111 010010010010 11 010100100100 11 0010100100100 111

Interpreting this as a binary string, we find that the serial number of
this TM is 128,173,980,461,351.

€ Given the serial of a TM, we can reconstruct it uniquely.

€ Not all binary strings are encoding of TMs.

Encoding Strings

String Code

empty 1
0 2
1 3
00 4
01 5
10 6
11 7
000 8
001 9
010 10

. . . and so on.

Again, we can reconstruct the string uniquely from its code.

A Program as a Function on Positive Integers

So What?

Let's construct a matching, P, from all binary strings to the strings
empty and '0'.

(1) List all TMs (that's all programs, under the clear box definition)
in increasing order of their serial numbers. Call them M1, M2, . . .

(2) For all positive integers, n,

(a) Find the string, sn, with code n.

(b) Use sn as input to Mn and look at its output:

(i) If Mn, on input sn, produces no output (that is, it leaves
its tape blank), then match sn to '0'.

(ii) If Mn, on input sn, produces any output, including
infinite output, then match sn to the empty string (that is,
all blanks).

What have we done?

€ We have produced a black box definition, P, that cannot possibly be
realized by any clear box TM program.

P can't be realized by M1, since P was designed to behave differently
from M1 on input s1.

P can't be realized by M2, since P was designed to behave differently
from M2 on input s2.

. . . and so on, for all machines.

€ In simple terms:

There is at least one input-output matching that cannot be realized by
any Turing Machine.

€ Or, said differently,

The black box definition of computability contains strictly more than
the clear box definition.

So What (Part 2)?

There is a matching between inputs and outputs that cannot be realized
by a TM (and hence, by Church-Turing, by any program).

€ So, there are things that computers cannot do.

(Since infinity comes in different sizes.)

€ We have no finite way of describing what the impossible matching P is.

Q: Are all the impossible computational tasks undescribable?

A: Nope.

The Halting Problem

Design a program, H, that will do the following:

(1) Take as its input a description of a program P (in binary, say),
along with a sample input, s, for P.

(2) Halt eventually and answer "yes" if P will eventually halt when
given input s, or halt and answer "no" if P will run forever when given
input s.

Specification for H:

H will always halt and give the correct answer, no matter what P and s
are.

Why H Is Impossible

Suppose H were possible to write. Use H as a subroutine in another
program H', which acts as follows:

(1) H' takes a binary string x as input and feeds x to H as both the
description of a program and as a possible input.

(There's nothing peculiar about a program being fed its own description
as input‹we could use a word processor to edit its own code, for
example.)

(2) If H answers "yes," H' will enter an infinite loop and run forever.
If H answers "no," H' will stop.

H' is a somewhat peculiar object, but it certainly is a program, if H
is.

€ H', when given an encoding, x, of a program, will halt if and only if the
program x will not halt when given its own encoding as input.

What happens when we feed H' its own description?

€ Putting H' in place of x in the description above gives:

+ H', when given its own encoding, will halt if and only if it will not
halt when given its own encoding.

€ In other words, if H' is a program, there is at least one input for which
H' will halt if and only if it doesn't halt!

€ This contradictory behavior cannot be. The only conclusion possible is
that we were wrong when we assumed H was a program. So, H is impossible.

€ Self-referentiality is a real problem with programs.

€ Rice's Theorem says, "Any nontrivial property of programs is
undecidable."

€ It is very rarely the case that we can write programs to answer questions
about programs.