CP1300 Theory

(Sections 11.*)
Last modified Wednesday, 25-Oct-2000 23:12:47 UTC.

Content

Computability
- Problems range from simple (and computable) to noncomputable.
- The Halting Problem
  A program (or function), called H, that solves the Halting Problem takes as input any program P and any input X for P. H outputs TRUE if P would halt when given input X, and outputs FALSE otherwise (e.g., if P would go into an infinite loop).
  For example, Loop.cpp:
```
          #include 
          #include 

          int main(int argc, char *argv[]) {

          int Index;

          Index = atoi(argv[1]);
          while (Index != 0)
              Index--;

          return(0);
          }
          
```
  does not halt for input X = -1, but does halt for input X = 5. So running H("Loop.cpp",-1) should output FALSE, and H("Loop.cpp",5) should output TRUE.
- A solution for the halting problem must work for all programs and all inputs. For some programs the analysis is easy, e.g.,
```
          #include 

          int main(int argc, char *argv[]) {

          while (TRUE) ;
    
          return(0);
          }
          
```
  will obvious never halt for any input. Similarly,
```
          #include 

          int main(int argc, char *argv[]) {

          return(0);
          }
          
```
  will always halt for any input. Of course, most programs are a lot more complicated so solving the halting problem in general is harder than this.
- The Halting Problem is Noncomputable
  We can prove that no matter how hard we try we will not be able to find a program that solves the halting problem. That is, the halting problem is noncomputable.
  - Assume that we actually have a program H that solves the halting problem.
```
H(P,X) = True   if P halts when given input X
       = False  if P does not halt when given input X
               
```
  - Show that if H exists then contradictions are provable. Hence H does not exist.
  - Construct a new program called I that takes as input a program P:
```
I(P) {
if (H(P,P))
    while (TRUE) ;
else return(TRUE);
}
               
```
    - I determines whether P does not halt when given itself as input.
    - I will go into an infinite loop if P does halt when given itself as input.
```
I(P) = True     if P does not halt when given input P
       Loops    if P halts when given input P
                    
```
  - Now try to determine the value of I(I) : will I halt when given I as input. There are two cases to consider:
    - I(I) returns TRUE and halts
      - This means that H says that I does not halt when given I as input.
      - Contradiction
    - I(I) goes into an infinite loop.
      - This means that H says that I halts when given I as input.
      - Contradiction
    - Conclude that program I cannot exist.
  - I is constructed from H, so H cannot exist
  - The halting problem is noncomputable.
- Other Noncomptable Problems
  - The Totality Problem
    A program, called T, that solves the Totality Problem takes as input a program P. T outputs TRUE if P would halt when given any possible input, and outputs FALSE otherwise.
    If the Totality Problem could be solved, then so could the Halting Problem. Therefore the Totality Problem is noncomputable.
  - The Equivalence Problem
    A program, called E, that solves the Equivalence Problem takes as input two programs P and Q. E outputs TRUE if, given any input, P and Q produce the same output, and E outputs FALSE otherwise.
    If the Equivalence Problem could be solved, then so could the Totality Problem. Therefore the Equivalence Problem is noncomputable.

Time Complexity and Big-O Notation (p.433)

Fibonacci numbers
- The 1st Fibonacci number is 0
- The 2nd Fibonacci number is 1
- The Nth Fibonacci number is the (N-1)th + (N-2)th Fibonacci numbers, for N > 2.
- The Fibonacci series is
  0, 1, 1, 2, 3, 5, 8, 13, ...
- RecursiveFibonacci.cpp - Computing the Nth Fibonacci number using the definition directly.
- Observe that it can be done linearly. LinearFibonacci.cpp - Computing the Nth Fibonacci number linearly.
- What's the difference? How big is the difference?
Consider this code for adding 7 to each element of an array:
```
for (Index = 0; Index < N; Index++)
     TheArray[Index] = TheArray[Index] + 7;
          
```
How long will it take on a computer?
- The operations performed are:
  - Index = 0 - once
  - Index < N - N times
  - TheArray[Index] = - N times
  - + 7 - N times
  - Index++ - N times
- The time taken is dominated by the things done N times, i.e., is proportional to N. It's linear. The proportion depends on the computer time to do <, +, ++
Consider this code for multiplying each element by 2 and adding 7:
```
for (Index = 0; Index < N; Index++)
     TheArray[Index] = TheArray[Index] * 2 + 7;
          
```
How long will it take on a computer?
- The only change is * 2 - N times. The time is taken is still proportional to N.
- The Big-O notation says this code is O(N). This is short hand for saying "proportional to N", and indicates linear complexity. This is commonly said as "order N".

Orders of magnitude

Given an array of N integers, how complex is:
- Add 1 to the first element. Write down the result.
- Look at the middle element; if it is odd then repeat this operation on the top half of the array, otherwise repeat it on the bottom half of the array, until the portion of the array being used has only one element. Write down that last element.
- Add 7 to each element. Write down each result.
- For each element do the operation of recursively looking at the middle element, described above, but making the decision based on the polarity of the difference between the middle element and the element under consideration.
- For each element, multiply it by each other element. Write down each result.
- Write down 0. For each element of the array, write down the sum and difference between the element and each value written down when using the previous element (starting with 0 the first time round).

The major groups of time complexity are: (p.439)

Constant	O(1)
Logarithmic	O(log_b(N))
Linear	O(N)
N log N	O(N * log_b(N))
Polynomial (of a given order)	O(N^m)
Exponential	O(k^N)

The differences due to the factors of proportion are insignificant compared to the differences caused by higher complexity. (p.436)

3 3 3 3 3 3 Constant
log₁₀N 0 1 2 3 4 Logarithmic
Base 10
3 * log₁₀N 0 3 6 9 12
log₂N 0 3.32 6.64 9.96 13.29 Logarithmic
Base 2
10 * log₂N 0 33.2 66.4 99.6 132.9
N 1 10 100 1000 10000 Linear
2 * N 2 20 200 2000 20000
200 * N 200 2000 20000 200000 2000000
N * log₁₀N 0 10 200 3000 40000 N log N
N² 1 100 10000 1000000 100000000 Polynomial
Order 2
100 * N² 100 10000 1000000 100000000 10000000000
N⁵ 1 100000 10000000000 10¹⁵ 10²⁰ Polynomial
Order 5
2^N 2 1024 1.26765 * 10³⁰ eeek mega eeek Exponential

The factors of proportion can be omitted for large enough data. This is always assumed in Big-O analysis.
The smaller order complexities in a sum can be omitted for large enough data. This is always assumed in Big-O analysis.

3	3	3	3	3	3	Constant
log₁₀N	0	1	2	3	4	Logarithmic Base 10
3 * log₁₀N	0	3	6	9	12
log₂N	0	3.32	6.64	9.96	13.29	Logarithmic Base 2
10 * log₂N	0	33.2	66.4	99.6	132.9
N	1	10	100	1000	10000	Linear
2 * N	2	20	200	2000	20000
200 * N	200	2000	20000	200000	2000000
N * log₁₀N	0	10	200	3000	40000	N log N
N²	1	100	10000	1000000	100000000	Polynomial Order 2
100 * N²	100	10000	1000000	100000000	10000000000
N⁵	1	100000	10000000000	10¹⁵	10²⁰	Polynomial Order 5
2^N	2	1024	1.26765 * 10³⁰	eeek	mega eeek	Exponential

Some examples (p.438)

for (k=1; k <= n/2; k++) {
    for (j=1; j <=n*n; j++) {
        Do Something
        }
    }

for (k=1; k <= n/2; k++) {
    Do Something
    }
for (j=1; j <=n*n; j++) {
    Do Something
    }

k = n;
while (k > 1) {
    Do Something
    k = k/2;
    }

Space Complexity
- The complexity of a program can also be measured in terms of how much memory it needs.
- There are known relationships between time and space complexity, and often one can be traded for the other.

Turing Machines

When we discuss an algorithm we have to write it down.
- The notation plays a big part in how understandable the algorithm is etc.
- We have written algorithms down as numbered English steps while we design them. This is one notation for an algorithm.
- Once we have refined our design enough we translate our algorithm into C++. Thus C++ is another (more formal) notation for algorithms.
Computer scientists and mathematicians have defined lots of different ways of writing algorithms.
- There are many different programming languages.
- More theoretically, there are mathematical notations that also serve to describe algorithms.
- Even though there are many different ways to write algorithms it seems likely that they are equivalent. This notion is called the Church-Turing thesis and is named after the two people who pioneered a lot of this theoretical work.
Informally, the Church-Turing thesis can be stated as the following two statements:
- All reasonable definitions of "algorithm" which are known so far are equivalent.
- Any reasonable definition of "algorithm" which anyone will ever make will turn out to be equivalent to the definitions we know.
No-one has proven the Church-Turing thesis, but no-one has disproved it either and it is widely accepted to be true.
If we believe the Church-Turing thesis we can talk of "algorithms" in a general way without having to worry too much about precisely what they are.
Alan Turing was a pioneer of Computer Science and one of his main contributions is the Turing Machine.
- This isn't a real machine like a PC or a DECstation
- It is a hypothetical one.
- It is interesting because it is a very simple machine but it turns out to be powerful enough to compute anything that much more complex computers can compute.
- Much of the theory of computer science is concerned with studying the properties of Turing Machines.
A Turing Machine consists of a tape and a control unit. The tape is used to store information stored in tape squares and can be thought of as similar to the main memory or secondary storage in computers that we use.
- Tape squares are similar to the memory locations in a real computer.
- The control unit is similar to a CPU.
- To connect the control unit and the tape there is a read/write head by which the control unit can read what is on the tape or write new information on the tape.
- The tape can be moved to the left or the right so the head can access all parts of the tape.
The control unit uses a state table.
- The state table is an array indexed by the current state and the symbol that is in the tape square underneath the read/write head.
- The entry in the table is a state and an action to perform.
To begin a computation using a Turing machine we
- Put a string of symbols onto the tape. These symbols are the input to the computation.
- Put blanks in all unused tape squares
- Make the read/write head point to the leftmost input symbol.
- The control unit starts in a state S.
- At each step of the computation the control unit performs the following:
  - Puts the control unit into a new state determined by the machine's state table.
  - Performs the action specified by the state table. That is one of:
    - Writes a symbol in the tape square underneath the read/write head, replacing the one already there.
    - Moves the tape head to the left or the right.
- There is a special halt state H; when the machine reaches state H computation stops.
- The output of the computation is on the tape.
- It may seem that a Turing machine can't do much.
- As noted before it can do anything that our much more complicated computers can do.

A Turing Machine Program

Assume that we have a string consisting of A's and B's and we want to convert all of the B's into A's.
To solve this problem with a Turing machine we need a state table.
- What we need to do is examine the symbol under the read/write head.
- If it's an A then we can move to the next symbol
- If it's a B then we need to change it to an A and move to the next symbol.
- Because we cannot write a symbol and move in one step we need another state to encode this information.

Here is a state table for our machine:

Data
State A B ' '
S S
Move right S1
Write A H

S1 S
Move right

Let's assume that the input is ABBA and see what the Turing machine does.

State #
S A B B A

State #
S A B B A

State #
S1 A A B A

State #
S A A B A

State #
S1 A A A A

State #
S A A A A

State #
S A A A A

State #
H A A A A

Programming computers is a complex activity.
- Usually there is a relatively complex programming language involved
- Programs are executed on a complex piece of hardware.
- Different people like different programming languages and buy different machines.
- It can be hard for theoreticians to talk about computation in abstract terms unless they can agree on the programming language to use and the machine on which to run programs.
- Turing machines are useful because they are an abstract model of computation that can be used as a common base by theoreticians.

	Data
State	A	B	' '
S	S Move right	S1 Write A	H
S1	S Move right

State	#
S	A	B	B	A

State		#
S	A	B	B	A

State		#
S1	A	A	B	A

State			#
S	A	A	B	A

State			#
S1	A	A	A	A

State				#
S	A	A	A	A

State					#
S	A	A	A	A

State					#
H	A	A	A	A

Self assessments

Tutorial Questions

Turing Machines

Exam style questions

O(N^m) is called "polynomial complexity". What are the following complexities called?
- O(1)
- O(log_bN)
- O(N)
- O(N*log_bN)
- O(k^N)

What is the complexity, in big-O notation, of the following C++ code fragment?

Index = N;
Total = 0;
while (Index > 1) {
    Total += Index;
    Index =/ 2;
    }
for (Index = N; Index > -N; Index--)
    Total += Index;

What is "The Totality Problem" in computing theory? Can you provide an algorithm for solving this problem?
Positive integers can be represented by strings of A's, where the number of A's is the number represented. For example, the string "A" represents the number 1, the string "AA" represents the number 2, and so on. Using this way of representing integers, write a Turing machine state table to add 1 to an integer. Assume that the representation of the integer is on the tape and that the machine starts out in state S with the head looking at the first symbol of the integer. At the end the machine must be in state H and the tape must contain the representation of the result.