ch 18.txt

We want to know what the limitations of the problem-solving capabilities of computers.

We want to know what kinds of problems can be solved on a computer in a reasonable time, using a reasonable amount of memory.

A Turing machine consists of a tape (that extends infinitely in both directions), a read/write head that moves at the direction of the control unit, and a control unit that keeps track of what "state" the machine is in, directs the tape to move (and in which direction), and whether and what the head should write.

• The control unit keeps track of the state of the machine (what it is currently doing), then evaluates the current symbol under the read/write head to make 3 determinations:
• 1) determine which symbol to place in the current cell
• 2) determine whether to move the read/write head one cell to the left or right, and
• 3) determine the next state of the machine

state transition diagram

The Church-Turing Thesis states that the set of functions that can be calculated on a computer is exactly the same as the set of functions for which a Turing machine can be devised.

The Halting Problem has been proven to be non-computable. It asks: given a program with a set of input values, does the program halt on that input, or does it get stuck in an infinite loop?

It is a measure of how many steps are executed when the associated program is run. (Big O notation)

• It provides information regarding the program's "order of complexity".
• O(1) -> execution time doesn't relate to the size of the number n.
• O(n) -> execution time increases linearly as n increases
• O(n*squared) -> execution time increases quadratically as n increases

• *logarithmic - number of steps in its execution is bounded by a logarithmic function (k ln(n))
• *polynomial - number of steps in its execution is bounded by a polynomial function (ix^2+jx+k)
• *exponential - number of steps in its execution is bounded by an exponential function (k*2 to the n)

When you perform a small number of calculations, you can use an algorithm that is costly in time and not be penalized too much. But if you apply the same algorithm to a large number of calculations, the problem may take so long on your machine that it is effectively incalculable.

You have a knapsack that can hold up to W weight; no more than that. Given a set of jewels, each of which has a weight w and a price p, pack the maximum worth of gems into the knapsack without exceeding its capacity.