Complexities

Time Complexity(informal):

Given a Turing Machine $\ \QTR{Large}{M}$ that halts on all inputs, the time complexity of $\QTR{Large}{M\ }$ is the function

where:

number of steps such that $\QTR{Large}{M}$ halts on an input of length

Since Turing Machine alphabets are finite, hence there is only a finite number of strings of any length. is well defined:

Since Turing Machine implementations of functions will vary, and one is often most interested in the underlying function that

$\QTR{Large}{M\ }$ implements we are usually interested in
In fact, a typical application speaks to the existence of a Turing Machine implementation, $\QTR{Large}{M,}$ of a given function such that

constant time, linear time, polynomial time , logarithmic time , exponential, time.

Two Examples:

Thinking of the following polynomials as two Turing Machine implementations of the same function:

$\hspace{1.5in}$ 8 multiplications and 3 additions.

also

$\hspace{1.5in}$ 3 multiplications and 3 additions. (Horner's Method)

But

However, In discussing the complexity of the underlying function we are interested Horner's Method, in particular : $\smallskip$

Towers of Hanoi Revisited- 5 Disk Output:

1AB2AC1BC3AB1CA2CB1AB4AC1BC2BA1CA3BC1AB2AC1BC5AB1CA2CB1AB3CA1BC2BA1CA4CB1AB2AC1BC3AB1CA2CB1AB

The Pegs:

A-B A-C B-C A-B C-A C-B A-B A-C B-C B-A C-A B-C A-B A-C B-C A-B C-A C-B A-B C-A B-C B-A C-A C-B A-B A-C B-C A-B C-A C-B A-B

The Disks:

1213121412131215121312141213121

__________________________________________________________________

Space Complexity(informal):

Given a Turing Machine $\ \QTR{Large}{M}$ that halts on all inputs, the space complexity of $\QTR{Large}{M\ }$ is the function

where:

number of cells scanned such that $\QTR{Large}{M}$ halts on an input of length

The largest number of tape cells a Turing machine visits on all inputs of a given length
How much memory is required to do a calculation where the input is of a given size

__________________________________________________________________

Descriptive or Kolmogorov Complexity(informal):

Given a Universal Turing Machine $\ \QTR{Large}{U\ }$ there will be different Turing Machines implementation strings that produce.a given output.

Provisional Definition: For a given output string let $\QTR{Large}{<M>\ }$ be an input string for $\QTR{Large}{U}$ , such that $\QTR{Large}{U\ }$ halts with $\QTR{Large}{x\ }$ on the tape

Descriptive or Kolmogorov Complexity

all $\QTR{Large}{<M>}$ that halt with $\QTR{Large}{x}$ on the tape.

Notes:

There is a constant such that for all $\QTR{Large}{x}$

Just choose such that it halts as soon as it starts basically one instruction:
The Towers of Hanoi and Huffman Coding ;