keeping simple

Category: theory

  • Process algebra is based on a misunderstanding of automata theory

    See the current pdf in Arxiv 

    Robin Milner’s book Communication and Concurrency involves a take on state machines that is fundamentally incorrect.

    “Now in standard automata theory, an automaton is interpreted as a language i.e. as a set of strings over the alphabet.“

    That’s not at all correct, but let’s accept the claim for now and follow the argument. Consider two state machines A and B with an alphabet of events  {a,b,c,d}  and A has states {A,A1,A2, A3} and B has states {B,B’,B1,B2,B3}. The state machine transitions can be given by ordered triplets (state1,input, state2) that show the input label  on a directed edge between state1 and state2.  For Milner’s example:

    state machine A has transitions { (A,a,A1), (A1,b,A2), (A1,c,A3), (A3,d,A) },

    state machine B has transitions: { (B,a,B1) (B,a,B’), (B1,b, B2), (B’,c,B3), (B3,d,B)}.

    B is non-deterministic because there are 2 “a” transitions from state B. Milner points out that if we consider A2 and B2 to be accept states, both machines accept the same language (acd)*ab. So far so good. At this point Milner asks us to think of {a,b,c,d} as “ports” or maybe buttons that can be pushed. The button “is unlocked if the agent can perform the associated action and can be depressed to make it do the action, otherwise the button is locked and cannot be depressed.”  Then: “after the a-button is depressed a difference emerges between A and B. For A – which is deterministic – b and c will be unlocked, while for B – which is non-deterministic – sometimes only b will be unlocked and sometimes only c will be unlocked.” If you don’t look carefully, you’ll miss a subtle change of conditions that has significant ramifications.

    An experimenter or external agent trying to push these buttons will discover a difference between the two machines eventually because sometimes after an initial “a” input on the second state machine a “b” is possible and sometimes not, although on the first state machine after an “a” the “b” is always possible.  But how does the external agent determine that B will not perform a “b” action sometimes? The external agent “attempt[s] to depress b” and fails – the locked/unlocked state of each button is visible to the external agent. So Milner has changed definitions in the middle of the argument.  At the start, finite state machines were language recognizers with, as the classical text on automata theory explains: “output limited to a binary signal: ‘accept/don’t accept’ ” [Hopcroft and Ullman].  Those automata will not tell us  anything else about a word other than that binary condition: is it in the language or not.  But Milner’s button state machines tell us also what buttons are locked and what are unlocked in the terminal state reached by the word.  So Milner’s state machines distinguish words that a recognizer state machine does not. In fact, these Milner state machines have 5 binary outputs in each state – indicating the locked/unlocked status of each button plus accept/don’t accept. State machines with more than a binary output alphabet are called Moore or Mealy machines in poor old standard automata theory.

    Standard automata theory does not “interpret” state machines  “as a language” but there is a theorem that the class of languages recognized by those finite state binary output deterministic state machines is the same as the class of languages recognized by finite state non-deterministic state machines. Two  machines that recognize the same language may be distinct in many other ways (there is a whole theory of state machine minimization important in digital circuit design).   And state machines that have additional outputs (sometimes called “transducers”) are essentially descriptions of maps from input strings to output strings or from input strings to output value in the terminal state \(M:E^*\to X^*\). Standard automata theory would say Milner’s two machines accept the same language of strings, but produce different languages of strings.

    Standard automata theory, as far as I know, has never really considered the case of non-deterministic Moore machines but the extension is trivial. Milner’s transition systems are just labeled directed graphs with a root vertex – state machines. Each vertex is a state. The output of a state is a the set of labels that label edges starting at that state plus a  binary accept value. Associate each finite sequence of labels with a set of possible vertexes that can be reached from root vertex following the sequence of labels and construct a set of pairs (s,Q) for each sequence s so that Q is that set of possible destinations.    As far as I can tell on a quick look, Milner’s bisimulation is simply equality of  those sets of pairs between two of these graphs.

    State machines represent composition and communication in terms of automata products

    Another common argument in the process algebra literature is that automata cannot express interaction. Here’s a relatively complete argument.

    The simplest model of behaviour is to see behaviour as an input/output function. A value or input is given at the beginning of the process, and at some moment there is a(nother) value as outcome or output. This model was used to advantage as the simplest model of the behaviour of a computer program in computer science, from the start of the subject in the middle of the twentieth century. It was instrumental in the development of (finite state) automata theory. In automata theory, a process is modeled as an automaton. An automaton has a number of states and a number of transitions, going from one state to a(nother) state. A transition denotes the execution of an (elementary) action, the basic unit of behaviour. Besides, there is an initial state (sometimes, more than one) and a number of final states.A behaviour is a run, i.e. a path from initial state to final state. Important from the beginning is when to consider two automata equal, expressed by a notion of equivalence.

    On automata, the basic notion of equivalence is language equivalence: a behaviour is characterized by the set of executions from the initial state to a final state. An algebra that allows equational reasoning about automata is the algebra of regular expressions (see e.g. [58]). Later on, this model was found to be lacking in several situations. Basically, what is missing is the notion of interaction: during the execution from initial state to final state, a system may interact with another system. This is needed in order to describe parallel or distributed systems, or so-called reactive systems. When dealing with interacting systems, we say we are doing concurrency theory, so concurrency theory is the theory of interacting, parallel and/or distributed systems.[BAETTEN]

    We see the same argument about language equivalence discussed above and a second argument about interaction that is actually more difficult to understand. Here is a product of automata in which each automaton can communicate with (interact with) each other automaton from a paper published in 1962.

    Definition 1. Let {M1, M2.. ., Mn} be a set of Moore type machines in which the outputs of any machine Mi i = 1, 2,…, n, may be used as inputs to other machines. We shall say that this set of interconnected machines is concurrently operating if the next state (state at time t + 1) of each machine Mi depends on the present state of Mi, the present outputs (which depend only on the present states) of the machines to which it is connected, and the present external input. The ordered n-tuple (or “configuration”) of the present states of the machines M1 M2 . . ., Mn will be referred to as the state of the interconnected machine.[LOOP]

    This product is certainly flexible enough to describe any type of communication. In fact, it can easily accommodate the type of synchronous message passing considered fundamental in the process algebras. Suppose we have Moore type state machines that output requests to send and receive messages on channels. Put n of them together in a product of the type Hartmanis defines and add another state machine to act as a scheduler. The input to the scheduler is the set of requests of the other machines. The output of the scheduler is a prioritization of the other factor machines. The highest priority machine then can act by either using the external input or the output of a communicating factor machine – which will also make a transition.

     

    [MILNER] A calculus of communicating systems, Robin Milner. Springer (LNCS 92), 1980. ISBN 3-540-10235-3

    [MILNER2] The Polyadic pi-Calculus: a Tutorial (1991)

    [RABINSCOTT] M. O. Rabin and D. Scott, “Finite Automata and their Decision Problems”, IBM Journal of Research and Development, 3:2 (1959) pp.115-125.

    [HARTMANIS] Hartmanis, J.; and Stearns, R. E. (1966), Algebraic Structure Theory of Sequential Machines (Prentice Hall)

    [LOOP] Juris Hartmanis: Loop-Free Structure of Sequential Machines Information and Control 5(1): 25-43 (1962)

    [HALGEBRA] Hoare, C. A. 1993. Algebra and models. In Proceedings of the 1st ACM SIGSOFT Symposium on Foundations of Software Engineering (Los Angeles, California, United States, December 08 – 10, 1993). D. Notkin, Ed. SIGSOFT ’93. ACM, New York, NY, 1-8. DOI= http://doi.acm.org/10.1145/256428.167053

    [HENNESSY] Hennessy, M. and Milner, R. 1985. Algebraic laws for nondeterminism and concurrency. J. ACM 32, 1 (Jan. 1985), 137-161. DOI= http://doi.acm.org/10.1145/2455.2460

    [BAETEN] Baeten, J. C. 2005. A brief history of process algebra. Theor. Comput. Sci. 335, 2-3 (May. 2005), 131-146. DOI= http://dx.doi.org/10.1016/j.tcs.2004.07.036

  • Practical State Machines for Computer Software and Engineering

    Download paper.

    [gview file=”https://www.yodaiken.com/wp-content/uploads/2016/01/practical.pdf”]

  • Theories of abstract automata – Arbib

    We have said that automata theory deals with the realization of partial functions F: X* —» Y* by some finitely specifiable substrate. Before we specify in more detail the forms (of which the Turing machine is one) of substrate which have figured most prominently in automata theory, it is useful to distinguish on-line machines from off-line machines. An on-line machine is one that may be thought of as processing data in an interactive situation—in processing a string it must yield a continual flow of outputs, processing each symbol completely (albeit in a way dependent on prior inputs) before it reads in the next symbol. This means that the corresponding function F: X* —> F* must have the following special property:

    1 For each nonempty string u of X* there exists a function Fu: X* —» Y* such that for every nonempty v in X*
    F(uv) = F(u) • Fu(v) that is, the input string u causes the machine to put out the string F(u) and to “change state” in such a way that it henceforth processes inputs according to a function Fu determined solely by F and u. We call a function sequential if it satisfies property 1.

    From: Arbib, M.A., 1969,Theories of Abstract Automata, Prentice-Hall: Englewood Cliffs, N. J., 412 + xiii pages.

  • Algebra for computer science and function nesting

    The fundamental mathematical basis of computer science is that code and data are the same things. A sequence of bits can represent real numbers, integers, vectors, groups, matrices, video , audio, or programs, algorithms or even proofs. When we try to describe these systems mathematically, then it should not be surprising when we encounter a value that is also a map and a map with an image that consists of more maps.  For example, in a UNIX/MULTICS type file system if the file system is represented by a map F:Paths → Data, the data for a directory could also be considered to be or to represent a map. If F(home/snowden/passwords) is block of text, then F(home/snowden) is or encodes a map from strings to some information about where to find the file. In the original UNIX file systems F(home/snowden) is a map from strings to inode numbers. So (F(home/snowden))(passwords) is the inode number of the file that contains the passwords. UNIX style tree structured file systems are generally embedded in simpler file systems that map inode numbers to file contents S:Inode → Data. So the resolution of file names to data involves something like this

    F(home/snowden/passwords) =  S(S(S((S(root)(home)))(snowden))(passwords)))

    In more detail:

    i1 = S(root)(home); i2 = S(i1)(snowden);  i3 = S(i2)(password);

    data = S(i3). 

    This kind of construct is familiar to programmers, but seems weird in math even though it’s well defined and not all that deep.

     

  • Primitive recursion over words

     

     

    From:

    @book{Peter:1982:RFC:539249,
 author = {Peter, Roezsa},
 title = {Recursive Functions in Computer Theory},
 year = {1982},
 isbn = {0470271957},
 publisher = {Halsted Press},
 address = {New York, NY, USA},
}

    rozapeter

  • Pointers draft

    Despite pedants, pointers are useful and interesting and if you don’t understand them, you don’t really get what’s going on in a computer. Think of memory as a function $latex M: N\to N$ where $latex N$ is the set of non-negative integers. When we build physical memories, there are limits on both domain and range, but let’s ignore that for now. We can call the elements of the domain “addresses” and the elements of the range “contents”, but  they are both just non-negative integers.   A list of numbers, maybe phone numbers, could be in memory as a sequence. Perhaps $latex M(x_0), M(x_0 +1) \dots M(x_0 +k)$ is the list.

    x0 2125551212
    x0+1 3015551212
    x0+2 7125551212
    …
    x0+k 5125551212

    Alternatively, that data could be scattered around memory in pairs of phone number and address of next phone number. Address and contents are just numbers. The memory may have contents $latex M(x_0) $ that is an address of other contents: $latex M(M(x_0)) $ is a perfectly reasonable expression. Here we are using the contents at one address to “point to” contents at another address. If $latex y_0$ is the address of the first such pair, the next pair is at $latex y_1 = M(y_0 +1)$ and the next after that is at $latex y_2 = M(y_1 +1)$. To make this more comprehensible define $latex Y(0) = y_0$ and $latex Y(n+1) = M(Y(n) +1)$ Then $latex Y(i)$ is the address of the $latex i^{th}$ pair and the $latex i^{th}$ phone number is $latex M(Y(i))$. The list of phone numbers is $latex M(Y(0)),\dots M(Y(k))$. It’s easy to screw this up (as the pedants note). If $latex M(Y(i)+1)$ is not the right address of the next element, following the chain could end up making a random tour of memory that would pull up who-knows-what as phone numbers.

     

  • Fischer Lynch Patterson and timeouts

    There is a widely cited (over 1400 cites in CiteseerX ) result called the Fischer-Lynch-Patterson text_message_from_godot-469763theorem about consensus – a key issue in distributed databases or any system where data is either distributed or replicated or both.

    In this paper, we show the surprising result that no completely asynchronous
    consensus protocol can tolerate even a single unannounced process death.

    As far as I can tell the “surprising” result is that unbounded delays are not bounded. Without timeouts, we can not distinguish between a site B that will eventually send a message to site A and a site B that has failed (crashed) and will never send a message.

    We do not consider Byzantine failures, and we assume that the message system is reliable it delivers all messages correctly and exactly once. Nevertheless, even with these assumptions, the stopping of a single process at an inopportune time can cause any distributed commit protocol to fail to reach agreement. Thus, this important problem has no robust solution without further assumptions about the computing environment or still greater restrictions on the kind of failures to be tolerated!
    Crucial to our proof is that processing is completely asynchronous; that is, we make no assumptions about the relative speeds of processes or about the delay time in delivering a message. We also assume that processes do not have access to synchronized clocks, so algorithms based on time-outs, for example, cannot be used. (In particular, the solutions in [6] are not applicable.) Finally, we do not postulate the ability to detect the death of a process, so it is impossible for one process to tell whether another has died (stopped entirely) or is just running very slowly.

    The Wikipedia summary is similar:

    In a fully asynchronous system there is no consensus solution that can tolerate one or more crash failures even when only requiring the non triviality property.[11] This result is sometimes called the FLP impossibility proof. The authors Michael J. Fischer, Nancy Lynch, and Mike Paterson were awarded a Dijkstra Prize for this significant work. The FLP result does not state that consensus can never be reached: merely that under the model’s assumptions, no algorithm can always reach consensus in bounded time. In practice it is highly unlikely to occur.

    I don’t get what is “significant” about this. It’s just a tautology wrapped in a complex formalism. If there is no upper bound on how long it can take for a node to send a message, and the only information passed between nodes is via message, then there is no way for one node to tell the difference between a delayed response and a response that will never come because the corresponding node has failed.

     

  • A hard theorem becomes easy over time.

    IMG_20140910_141117_570The basic result of the incompleteness proofs is pretty simple.  The proofs are complicated because the idea was literally unthinkable until programming was invented. The heroic efforts of Gödel, Skolem, Post, and Church to create a mathematics in which doing mathematics could be represented as some sort of calculation were an incredible feat of imagination. But today, programming is kind of obvious. So the general result should be simpler.

    Suppose we have a computer with an infinite memory that holds arbitrary integers and  can execute a simple programming language that consists of numbers. The key thing about the computer is that numbers in memory can be interpreted as integers or instructions, as we please. It’s certainly possible that the number encodes a program that makes no sense, but every program is just an integer and every integer encodes some program. Suppose that the computer has the usual arithmetic operations and conditionals plus recursion. Because numbers are programs,  we can have a number, say x, and a second number y and compute x(y) because x “encodes” some program.

    Programs as values, means that we can pass programs that compute functions as arguments to other functions.  For example we should be able to write “evaluate” so that “evaluate(x,y) = x(y)”. If f(x) = x*x then evaluate(f,5) = 25.  It would be useful to have a function “S”  which computes a “solution” to a function so that “S(f,x) = the smallest number y ≥ x  so that f(y)=0”. In fact, such a function is easy to define in our language: S(f,x) = ( if f(x)= 0 then x; else S(f,x+1) ). It is easy to see that S(f,x) will never terminate if there is no y ≥ x so that f(y)=0. For example if g(x) = x+1 then S(g,1) never terminates.  The question is whether we can write a function E(f,x) so that E(f,x) always terminates and so E(f,x)=1 if S(f,x) terminates and E(f,x)=0 if S(f,x) does not terminate. E doesn’t  find the solution, it just has to tell us whether S will find the solution. However, we can prove that we cannot write E with these specifications.

    The proof is by contradiction. Suppose we could write E. Then someone could write a “diagonal” program

    D(f) = { if E(f,f)=0 then 1; else S(f,f) }.

    So D(f) =1 if  E(f,f)=0;  there is no y ≥ f so that f(y)=0 but D(f) never terminates otherwise.  What about D(D) ? Does it terminate? If E(D,D)=0 then D(D) terminates with value 1. But if E(D,D)=0 then  for every y ≥ D, D(y) never completes. Which means D(D) does not terminate. So

    D(D) terminates with value 1 if and only if D(D) does not ever terminate.
    D(D) does not terminate if and only if D(D) does terminate.

    Assuming that the world makes logical sense ( a big leap) then  to get to this paradoxical result, we must have assumed something that is false: namely that we could somehow define E(f,x) so that it always terminates and correctly computes the answer to whether S(f,x) terminates.

    For mathematics, this result has all sorts of interesting implications. For example, if it were not true, we could, in principal, write a function that tested numbers to see if they were odd perfect numbers and marched up the positive integers until it found one. If that function could be evaluated by E, we’d know if there was such a number – something nobody seems to know right now. Any theorem Exists x, P(x) where P can be represented in  our language could be tested by evaluating E on a function that tests P on consecutive integers until it finds a solution. Any theorem Forall x P(x) could be evaluated by seeing if a program that looks for a
    counter-example ever terminates. All that should indicate that E is implausible as well as impossible. For computer science the implications are more subtle because the fact that we don’t really have computers with infinite memory matters in computer science.  That’s also interesting in pure mathematics: see Godel’s lost letter.

     

  • the terrible effect of Krohn-Rhodes

    One of the most interesting theorems in computer science is the Krohn-Rhodes theorem that shows a strong link between basic computer science and group theory. Crudely, the KR theorem extends Jordan-Holder \( (H_1 \triangleleft H_2 … \triangleleft H_n=G)\)  to state machines, but it does it in a way that doesn’t get us very far in understanding the structure of state machines. The problem is that the “division” is too restrictive. In terms of state machines, KR requires us to turn \( M\) into \( M_1 \rightarrow M_2\) where the input of \(M_2\) depends only on the system input and the output of \(M_1\).  This is called a “loop free” decomposition and Hartmanis-Stearns worked on it before KR teased out the underlying math. You can build a ripple carry adder that way and it makes sense that the simple devices that concerned early CS researchers seemed amenable to such a decomposition, but a few steps down the path and we come to systems that do not want to be decomposed into loop-free series at all. Consider a queue – when a new element is inserted each element needs the output of its neighbor to the back to get its new value – very nicely loop free. But consider a stack. A push makes each element take an input from its neighbor to the right and a pop makes each element take an input from its neighbor to the left.

    \[ \langle x_1, x_2 … x_n \rangle \mapsto[push\ y]\mapsto \langle y, x_1 \dots x_{n-1}\rangle \]

    \[ \langle x_1, x_2 … x_n \rangle \mapsto[pop]\mapsto \langle x_2 \dots x_{n},null\rangle \]

    In fact the stack is serially loop free – it has a nice loop free ordering per operation – but Krohn-Rhodes doesn’t go there (you could get to loop free by adding a counter to each element).  Anyways, the result is a theory that bounces off the observed or designed structure of computational objects and, at least to me, that designed structure is the interesting structure.

     

     

     

  • Gödel’s Lost Letter

    Gödel’s perspective in this letter is a refutation of the simplistic take on Turing’s proof seen so often in the computer science literature. In particular:

    After all, one would simply have to choose the natural number n so large that when the machine does not deliver a result, it makes no sense to think more about the problem

    Here is the letter:

    “One can obviously easily construct a Turing machine, which for every formula F in first order predicate logic and every natural number n , allows one to decide if there is a proof of F of length n (length = number of symbols). Let \(\psi(F, n)\) be the number of steps the machine requires for this and let \(φ(n) = max_F (F, n)\) . The question is how fast φ(n) grows for an optimal machine. One can show that φ(n) ≥ kn . If there really were a machine with \(φ(n) \sim k·n\) (or even \(\sim k·n^{2}) \), this would have consequences of the greatest importance [Tragweite]. Namely, it would obviously mean that in spite of the undecidability of the Entscheidungsproblem, the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine. After all, one would simply have to choose the natural number n so large that when the machine does not deliver a result, it makes no sense to think more about the problem. Now it seems to me, however, to be completely within the realm of possibility that φ(n) grows that slowly. Since (1) it seems that \(\phi(n)∼ kn \) is the only estimation which one can obtain by a generalization of the proof of the undecidability of the Entscheidungsproblem; and (2) after all \(φ(n) ∼ k·n\) (or \(∼ k· n^2 \)) only means that the number of steps as opposed to trial and error can be reduced from N to log N (or \((log N )^2 )\). However, such strong reductions appear in other finite problems, for example in the computation of the quadratic residue symbol using repeated application of the law of reciprocity. It would be interesting to know, for instance, the situation concerning the determination of primality of a number and how strongly in general the number of steps in finite combinatorial problems can be reduced with respect to simple exhaustive search.”

    ( Peter Clote’s translation of Godel’s letter to von Neumann from Sam Buss’s paper).

    See also Sipser’s paper which has a different translation of the letter.

    Here is Turing’s claim:

    I propose, therefore, to show that there can be no general process for determining whether a given formula U of the functional calculus Z is provable, i.e. that there can be no machine which, supplied with any one U of these formulae, will eventually say whether U is provable.

    It should perhaps be remarked what I shall prove is quite different from the well-known results of Gödel [15]. Gödel has shown that (in the formalism of Principia Mathematica) there are propositions U such that neither U nor –U is provable. As a consequence of this, it is shown that no proof of consistency of Principia Mathematica (or of Z) can be given within that formalism. On the other hand, I shall show that there is no general method which tells whether a given formula U is provable in Z, or, what comes to the same, whether the system consisting of Z with –U adjoined as an extra axiom is consistent.

    If the negation of what Gödel has shown had been proved, i.e. if, for each U, either U or –U is provable, then we should have an immediate solution of the Entscheidungsproblem. For we can invent a machine K which will prove consecutively all provable formulae. Sooner or later K will reach either U or –U. If it reaches U, then we know that U is provable. If it reaches –U, then, since Z is consistent (Hilbert and Ackermann, p.65), we know that U is not provable.

    Note: fixed Greek symbols March 16 2015

    Added Turing quote 10/1/2015