Art of Computer programming notation question

Question

I'm just starting to read TAOCP Volume 1 and I'm having trouble understanding the style.

Knuth mentions a computational method to be a quadruple (Q,I, Omega, f) -- but I am having trouble understanding what each of these is intended to be. I understand his first example, but don't understand his second

I'm looking at page 8 of the third edition.

---

Near the end of the chapter there is an algorithm that talks about sets of strings.

(I have replaced Greek variables with some easier to type ones -- sorry)

Let A be a finite set of letters, and let A* be the set of all string on A. The idea is to encode the states of the computation so that they are represented by strings of A*

Q = (s,j) where s is in A* and j is an integer, 0 <= j <= N 
I = subset of Q with j = 0
Omega = subset with j = N
f = function below  

(note that p & w are strings) If and s are strings in A*, we say that T occurs in s if s has the form pTw for strings p and w.

f(s,j) = (s,aj)             if Tj does not occur in s;
f(s,j) = (pYjw,bj)   if p is the shortest possible string for which s = pYjw
f(s,N) = (s,N)

I understand the concept of making sets of strings, but don't understand all that he is trying to say here. Why do I need Q, I, Omega? What is the f really explaining to me (why do I need 3 functions in f?)??

Can anyone help shed some light?

Zilber

Answer 1

Q = set of states (so that (s, j) represents state s at time j)
I = initial states (hence the requirement that j == 0)
Omega = final states (hence the requirement that j == N)
f = transition function

Also, there aren't three functions named f but rather f is piecewise-defined by three equations.

Engracia

I guess what I might be missing is how the 3 pieceswise functions achieve the overall goal? – Zilber

Answer 2

For full disclosure, I recently wrote an article on understanding Knuth's (pre-example) formal definition of an algorithm. A substantial portion of the below is just a copy/paste of the relevant text from the article answering your first question in depth;

Your first question on (Q, I, Ω, f)

---

Let us formally define a computational method to be a quadruple (Q, I, Ω, f), in which Q is a set containing subsets I and Ω and f is a function from Q into itself.

When Knuth refers to a computational method as a quadruple he is simply saying that a computational method is composed of four distinctly defined parts. He labels these four parts as (Q, I, Ω, f). He then moves on to briefly describe each component of this quadruple. I and Ω are sets (collections of things), and Q is also a set which contains the things in the sets I and Ω. At this point it’s easy to mistakenly assume that he means that Q contains only the sets I and Ω and nothing else. But we later find that this is not the case. Lastly he describes f as a function from Q into itself. What this means is that f is a process which takes an input which is an element from the set Q and returns or outputs another element from Q.

Furthermore f should leave Ω pointwise fixed; that is, f(q) should equal q for all elements q of Ω.

What this essentially means is that, what our function f returns, will be the same as its argument (i.e. the value will not change) if the argument is a member or element of (thing in) set Ω. This makes more sense when Knuth makes a clarification in his next statement; Spoiler alert - Ω is the set of possible outputs of our computational method. Once we know this it’s a little easier to understand. Passing an output back into our function will not change it.

The four quantities Q, I, Ω, f are intended to represent respectively the states of the computation, the input, the output, and the computational rule.

So Q is a set that contains all possible states of the computation i.e. all the possible variations of input, output and all the stages in between. The set I contains all possible inputs. The set Ω contains all possible outputs (sorry if I spoiled that revelation for you earlier). And finally, f represents the computational rule; that is, the process/es applied to each state to get the next state, eventually (hopefully) until we get our output.

---

To clarify, f represents a single function that has outputs defined based on its possible inputs. It only has three possible outputs in this specific example, and could have more (or less) in other algorithms. So, whats the purpose of defining the components of an algorithm in this way? By having them defined using formal notation they can also be analysed and subjected to mathematical examination when it comes to analysing specific algorithms.

Question about Treating the algorithm as a set of Strings

I answered another question on this subject here. But essentially what Knuth is doing here is using a Markov's algorithm to achieve what he has already described. It is worth studying (and working through a few examples of) Markov algorithms to help you understand exactly what is occurring here.

References

1. Markov's Algorithms Wiki
2. My Defining an Algorithm article.
3. Knuth the art of computer programming ex 1.1.8

Revolutionist

Answer 3

I'm not 100% sure, but it looks like Q is the set of all ordered pairs (s, j) for 0 <= J <= N. This will be your domain. It is the set of all possible states given some N and string s.

I is your subset of Q where all ordered pairs contain J=0, or your initial states. Omega is your subset of Q where all ordered pairs contain J=N, or your final states.

f is the actual function over domain Q.

EDIT

Think of the function definition being something along the lines of one function, but different cases depending on the given input. Think of a function you would writing in a language. ex:

tuple f(string s, int i)
{
    if (Tj not in s)
        (s, aj)
    else if ( p is shortest possible length such that s = pYjw)
        (pYjw,bj)
    else if ( i == N )
        (s, N)
}

Another example is the Fibonacci function definition. See how that is defined? Make sense?

Colorless

Answer 4

if u would have gone through the euclid's gcd algorithm that he stated earlier in the book. the idea is to mark the starting of each iteration as an initial stage and then define the number of states that will come in one iteration of loop (namely N). now as you will remember that we accepted the answer and halted the computation when the remainder of m divided by n equaled zero. i.e. we were searching for a particular occurrence of a string Yj. when the compuataion reaches itz final stage in the loop it is bound to halt or reiterate.

Dennisedennison

Answer 5

remember we are defining a 'computational method' and not an algorithm. what is a computational method naively?

a "procedure" that has all characteristics of an algorithm except that it possibly lacks finiteness, may be called a computational method.

simply put Q is a computational method.

Q = {all possible states of computations, I, Ω}
I = {all possible inputs}
Ω = {all possible outputs}
f = computational rule

f is a function from Q into itself.

f: Q  --->  Q
  [I]      [Ω]

f should leave Ω pointwise fixed which means:

f(q) = q, ∀ q ∈ Ω note it is not any different function but the same computationalrule just seperated to Ω

Now a procedure will have a sequence. And obviously, a computational method must also have a sequence. Hence,

Each input x in the set I defines a computational sequence x₀, x₁, x₂, ..., as follows: x₀ = x and x_k+1 = f(x_k) for k ≥ 0.

How x₀ = x? Don't forget the input x is a sequence and so the initial input sequence would be x₀. As we are dealing with a sequence, and when we are concerning about 'k' states, the order and the position of elements in the sequence matters. And so, the computational rule f is such that the position or more precise word 'state' of the k^th element would be k+1^th state. that way, we can seperately apply the function to each new state to get the state that follows.

if x_k+1 is not in Ω, then it makes no sense by definition of a function. Hence the wording of Knuth.

The computational sequence is said to terminate in k steps if k is the smallest integer for which x_k is in Ω and in this case, it is said to produce the output x_k from x.

Thus this is the definition of a computational method. the computational rule is the algorithm.

Maidstone

good answer, excepts "...input x is a sequence...". I think x itself is not a sequence. x is an input, and x defines a computational sequence. the reason why x0 = x, is because the computational sequence is a recursive procedure, and x is start point. – Heeley