Gödel's Lost 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 ψ(F, n) be the number of steps the machine requires for this and let φ(n) = maxF ψ(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) ∼ k·n (or even ∼ k·n2 ), 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 ψ(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· n2 ) 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

Godel's Lost 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 ψ(F, n) be the number of steps the machine requires for this and let φ(n) = maxF ψ(F, n) . The question is how fast φ(n) grows for an optimal machine. One can show that φ(n) ≥ k · n . If there really were a machine with φ(n) ∼ k · n (or even ∼ k · n2 ), 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 φ(n) ≥ k · n 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 · n2 ) 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 Gödel’s letter to von Neumann from Sam Buss’s paper)

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

Primitive recursion and transducers

11/23/2009 please see the updated version: here. Yet another version of the recursion/transducer paper . The main result is that simultaneous primitive recursion on strings corresponds to general products of state machines.

Rózsa Péter who developed much of recursive function theory
Rózsa Péter who developed much of recursive function theory (definitely smarter than Larry Summers)

Primitive recursion on strings is analogous to primitive recursion on integers where we define f(0) = constant and f(n+1) = g(f(n)). In strings the null string corresponds to 0 and appending a character corresponds to adding one so that “wa” is the string obtained by appending “a” to “w”. We can also easily define concatenation of strings: concat(w,nullstring)=w and concat(w,ua)= concat(w,u)a Primitive recursion is then:

f(nullstring)= x0

f(wa) = h(a,f(w))

You can produce a state machine from such a function trivially by associating each possible value of the function with a state: so there is a state  s= f(w) for each s in the image of f. Then the transition map  Next(s,a)=s’ if and only if h(a,s)=s’.  Let’s make an output function Output(s)=s, so we can get a specific type of state machine – a transducer – or state machine with output. And x0 is the initial state. Call this state machine Transducer(f).  Now if Transducer(f) is defined and g(w) = h(f(w)) then Transducer(g) can be Transducer(f) with a new output function – and then we can throw out any duplicate and unreachable states. If the output function of Transducer(f) is Output_f(s)=x then the new output function Output_g(s)= h(Output_f(s)). And it should be clear that for any state machine, finite or not, there is a corresponding function that can be constructed by primitive recursion on strings and composition.

Simultaneous recursion on strings works by defining two functions F and F* simultaneously (big surprise). Suppose we have g_1 … g_n which are all primitive recursive string functions. Then we can make the following somewhat peculiar definition

  1. F(w,i) = g_i(F*(w,i))
  2. F*(nullstring,i)= nullstring
  3. F*(wa,i) = concat( F*(w,i) , h(a,i,F(w,1) …, F(w,n)))

The idea is that F(w,i) is the output of component i when given the input F*(w,i) and also that h(a,i,F(w,1) …, F(w,n)) is the sequence (string) of events that happen to component i when “a” happens to the composite system in the state determined by “w”. This type of composition has a couple of nice properties.

  1. if G(w) = g(F(w,1) …, F(w,n)) then there is an H which can be constructed with just composition and ordinary primitive recursion on strings so that H(w)=G(w). In other words, simultaneous primitive recursion on strings doesn’t create any more state machines, it just tells us how to decompose (divide) state machines.
  2. If each g_i corresponds to a finite state machine then G corresponds to a finite state machine.
  3. F corresponds to a state machine that is the “general product” of the state machines corresponding to machines corresponding to g_i. I won’t go into details here, but the idea is that simultaneous primitive recursion is essentially a representation of a general automata product in the string function domain!  Read the paper if you want the details.
  4. There are some immediate implications for the monoids induced by the state machines and the monoid products induced by composition.

My main interest is in using this stuff to understand big state systems. But the coincidence of simultaneous primitive recursion on string functions corresponding to the general product of automata is good news in terms of validating that the mathematical basis has a structure and is not just a jury rigged construct held together by axioms and hope.

Deterministic multithreading

An interesting paper appearing in ASPLOS proceedings provides a “deterministic” locking method

Kendo enforces a deterministic interleaving of lock acquisitions and specially declared non-protected reads through a novel dynamically load-balanced deterministic scheduling algorithm. The algorithm tracks the progress of each thread using performance counters to construct a deterministic logical time that is used to compute an interleaving of shared data accesses that is both deterministic and provides good load balancing. Kendo can run on today’s commodity hardware while incurring only a modest performance cost ( http://www.gigascale.org/pubs/1883/asplos073-olszewski.pdf)

There is similarly motivated work on Java going on at UIC: http://dpj.cs.uiuc.edu/DPJ/Home.html

Both works refer to Lee’s paperwhich I discussed earlier. Nondeterministic threading is a  historical accident in computer engineering. Operating systems introduced time-sharing methods so single thread programs could be run in parallel during I/O delays and then so that multiple users could reasonably fairly share a processor and then so the OS and service programs could provide multiple services to a user at the price of slowing down user applications.  Exposing this system to users has been a mixed blessing. Certainly in the controls world, non-determinism is a dangerous fault.

IEEE's war on science

I dropped my subscription to the IEEE “Digital Library” because I found that if I strayed from a very narrow range of  areas, the IEEE wanted ridiculous fees for access to papers. For example, despite a subscription to the digital library, I was not entitled to papers in power engineering. Now I find that the IEEE is refusing to accept public domain papers for publication on the most dubious grounds. If the IEEE was charging simple access fees to papers – say a few dollars – it would be one thing, but at $18 or more per paper the IEEE is basically trying to create a wall around the material it got (for free!) from scientific workers and turn this material into a profit center.  It’s an absolute disgrace that poor students in Mozambique, not to mention Texas, are being extorted to pay for access to scientific data that was compiled at public expense and whose creators wanted it to be made generally available.

If the IEEE wants to be a profit making publisher, it should be forthwright about its intentions and then contributors to IEEE publications can consider whether they are being fairly compensated for their work.