We describe the design and implementation of an automatic computer controlled infusion pump for administering oxytocin to a woman in labor, with emphasis on the hardware and software safety issues. The infusion is applied by means of timed pulses, as opposed to the more usual continuous infusion method. The basic study of the system and its efficiency was described by R.J. Willcourt et al. (1894), while the mathematical algorithms employed were described by D. Pager and R.J. Willcourt (1995), and a patent for the system was granted earlier this year (D. Pager and R.J. Willcourt, 1996). The software safety issues encompass the detection by the system of various kinds of undesirable patient parameters, such as excessively high intrauterine pressure, constant intrauterine pressure, the occurrence of series of contractions closely following each other whose amplitudes are all exceedingly high. The hardware safety issues relate to the reliability of the system, and measures for ensuring that malfunctions are intercepted without the possibility of inappropriate infusion actions.

In this paper it is shown that whatever the length function employed, the problem of finding the shortest program for a decision table with two (or more) entries is not recursively solvable (whereas for decision tables with a single entry the problem is solvable for some length functions and unsolvable for others). Moreover, it is shown that there is a pair of finite sets of programs and a single entry E such that the shortest program for the decision table formed by adding a single additional entry to E is in all cases in one of the two sets, but it is undecidable in which. Some consequences of these results are then presented, such as showing that for a wide range of restrictions the results remain true, even when the repertoire of possible programs for a decision table is narrowed by only considering programs which meet certain restrictions.

The paper presents, as far as the author is aware, the first practical general method for constructing LR(k) parsers. It has been used, without computational difficulty, to produce LR(1), LR(2) and LR(3) parsers for grammars of the size of ALGOL.

Some ways of speeding up certain loops by software, firmware, and hardware means are discussed in this note. The importance of the inner loop calculation is emphasized and a simple, though as yet unused, programming technique is presented whereby the inner loop time may be reduced by approximately 20 percent. The general problem of a program with many loops is then considered and a method is indicated for obtaining the maximum speedup by means of the technique described earlier. Turning to firmware, it is shown how, by altering the normal algorithm used for the inner loop calculation, a very substantial speedup can be achieved with the use of microprogramming (above and beyond the savings in instruction decoding time). Finally, a means is considered whereby a computer can alter its own hardware, so as to achieve a speedup of several orders for loops in which the resolution of decision tables accounts for a significant portion of the iteration time.

A definition is given of the efficiency of an algorithm considered as a whole. This immediately raises the question of whether it is possible to find the most efficient or “optimum” algorithm. It is shown that an optimization problem of this kind is effectively solvable if and only if the set of arguments with which one is concerned is a finite one. Next, conditions under which an optimum algorithm does or does not exist are considered, and a limiting recursive process for finding it when it does is produced. Finally, some observations are made about the best space-time measure for algorithms which can be expected in certain cases. The results and proofs are couched in terms of Turing machines but may be adapted without difficulty to apply to other infinite digital machines such as the extensions of actual computers obtained by adding an infinite memory, or to the computations involved in other theoretical formulations of partial recursive functions such as those provided by Kleene's systems of equations or the URM's of Shepherdson and Sturgis.

The fundamental role of the restricted calculus of predicates in applications of symbolic logic, and particularly in Hubert's Beweistheorie as summed up by Hilbert and Bernays, makes it important that this logical calculus should be accurately defined. The first standard formulation of the calculus was that of Hilbert and Ackermann's Grundzüge der theoretischen Logik. This employed (in the first three editions) a finite set of axioms and rules of derivation, with rules of substitution included. A reaction by Hilbert and Ackermann's successors to persistent difficulty encountered with the rules of substitution has been to omit these rules, and instead enlarge the set of axioms and the other rules of derivation so as to encompass all possible substitutions. Such an enlargement seems to me to be undesirable. As an alternative, this note is designed to put the original approach of Hilbert and Ackermann for once and for all on a sound basis.