Floyd-Warshall

The algorithm is based on the following observation: , where i,j, and k are vertices and d(i,j) is the distance between i and j in the graph. Thus, by starting with a known set of edges, we can incrementally improve the shortest paths between any edges.

The pseudocode below assumes an input graph of N vertices. d(i,j) is if there is no edge from i to j, and the length of the appropriate edge otherwise.

for i = 1 to N
    for j = 1 to N
        dist[i][j] = d(i,j)

for k = 1 to N
    for i = 1 to N
        for j = 1 to N
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

The algorithm takes O(N3) time and O(N2) space, and has the distinct advantage of hiding a small constant in its behavior, since very little work is done in the innermost loop.

Turing Machines

The concept of the Turing machine is based on the idea of a person executing a well-defined procedure by changing the contents of an infinite number of ordered paper sheets that can contain one of a finite set of symbols. The person needs to remember one of a finite set of states and the procedure is formulated in very basic steps in the form of "If your state is 42 and the symbol you see is a '0' then replace this with a '1', remember the state 17, and go to the following sheet.".

More formally, a (one-tape) Turing machine is usually defined as a 6-tuple M = (Q,G,s,b,F,d)

• Q is a finite set of states
• G is a finite set of the tape alphabet
• s is the initial state
• b is the blank symbol
• F is the set of final or accepting states
• d is a partial function called the transition function, where L is left shift, R is right shift, S is no shift.

The following Turing machine has an alphabet {'0', '1'}, with 0 being the blank symbol. It expects a series of 1s on the tape, with the head initially on the leftmost 1, and doubles the 1s with a 0 in between, i.e., "111" becomes "1110111". The set of states is {s1, s2, s3, s4, s5} and the start state is s1. The action table is as follows.

 Old Read   Wr.      New     Old Read   Wr.      New
 St. Sym.   Sym. Mv. St.     St. Sym.   Sym. Mv. St.
 - - - - - - - - - - - -     - - - - - - - - - - - -
  s1  1  ->  0    R   s2      s4  1  ->  1    L   s4
  s2  1  ->  1    R   s2      s4  0  ->  0    L   s5
  s2  0  ->  0    R   s3      s5  1  ->  1    L   s5
  s3  0  ->  1    L   s4      s5  0  ->  1    R   s1
  s3  1  ->  1    R   s3

 Step State Tape   Step State Tape
 - - - - - - - -   - - - - - - - - -
    1  s1   11        9  s2   1001
    2  s2   01       10  s3   1001
    3  s2   010      11  s3   10010
    4  s3   0100     12  s4   10011
    5  s4   0101     13  s4   10011
    6  s5   0101     14  s5   10011
    7  s5   0101     15  s1   11011
    8  s1   1101       -- halt --

A universal Turing machine is Turing-complete. It can calculate any recursive function, decide any recursive language, and accept any recursively enumerable language. According to the Church-Turing thesis, the problems solvable by a universal Turing machine are exactly those problems solvable by an algorithm or an effective method of computation, for any reasonable definition of those terms.

It's often said that Turing machines, unlike simpler automata, are as powerful as real machines, and are able to execute any operation that a real program can

Turing machines would actually only be equivalent to a machine that had an unlimited amount of storage space. We might ask, then, why Turing machines are useful models of real computers. There are a number of ways to answer this:

1. Anything a real computer can compute, a Turing machine can also compute. Thus, a statement about the limitations of Turing machines (for instance, the minimum time required to calculate something) will also apply to real computers.
2. The difference lies only with the ability of a Turing machine to manipulate an unbounded amount of data. However, given a finite amount of time, a Turing machine (like a real machine) can only manipulate a finite amount of data.
3. Like a Turing machine, a real machine can have its storage space enlarged as needed, by acquiring more disks or other storage media. If the supply of these runs short, the Turing machine may become less useful as a model. But the fact is that neither Turing machines nor real machines need astronomical amounts of storage space in order to perform useful computation. The processing time required is usually much more of a problem.
4. Real machines are much more complex than a Turing machine. For example, a Turing machine describing an algorithm may have a few hundred states, while the equivalent DFA on a given real machine has quadrillions.
5. Turing machines describe algorithms independent of how much memory they utilize. There is a maximum to the amount of memory that any machine which we know of has, but this limit can rise arbitrarily in time. Turing machines allow us to make statements about algorithms which will (theoretically) hold forever, regardless of advances in conventional computing machine architecture.
6. Turing machines simplify the statement of algorithms. Algorithms running on Turing-equivalent abstract machines are usually more general than their counterparts running on real machines, because they have arbitrary-precision data types available and never have to deal with unexpected conditions (including, but not limited to, running out of memory).