An “Interchange Lemma” is proven, providing a new necessary condition for languages to be context-free. This “Interchange Lemma” is then used to show that the set of repetitive strings (i.e. strings of the form $xyyz$ with nonempty y) over an alphabet of three or more characters is not context-free—an issue which in the past has shown remarkable resilience against standard tools for proving languages not context-free and which has only recently been solved independently in [5] and [10]. The Interchange Lemma presented in this paper is a generalization of the proof technique used in [10].

We show that “looping” of while-programs can be expressed in Regular First-Order Dynamic Logic, disproving a conjecture made in [Harel-Pratt 1978]. In addition we show that the expressive power of quantifier-free Dynamic Logic increases when nondeterminism is introduced in the programs that are part of formulae of Dynamic Logic. Allowing assignments of random values to variables increases the expressive power even further.

We consider the problem of identifying an unknown value xε{1,2,...,n} using only comparisons of x to constants when as many as E of 'the comparisons may receive erroneous answers. For a continuous analogue of this problem we show that there is a unique strategy that is optimal in the worst case. This strategy for the continuous problem is then shown to yield a strategy for the original discrete problem that uses log2n+E.log2log2n+O(E.log2E) comparisons in the worst case. This number is shown to be optimal even if arbitrary “Yes-No” questions are allowed.

Restricted classes of programming systems (Gödel numberings) are studied, where a programming system is in a given class if every programming system can be translated into it by functions in a given restricted class. For pairs of systems in various “natural” classes, results are given on the existence of isomorphisms (one-to-one and onto translations) between them from the corresponding classes of functions. The results with the most computational significance concern polynomial time programming systems. It is shown that if $\mathcal{P} = \mathcal{N}\mathcal{P}$ then every two polynomial time programming systems are isomorphic via a polynomial time computable function. If $\mathcal{P} \ne \mathcal{N}\mathcal{P}$ this result points the way to the possible existence of “natural” but intractable computational problems concerning programming systems. Results are also given concerning the relationship between the complexity of certain important and commonly used properties of programming systems (such as effective composition of programs) and the complexity of translations into the systems.