Abstract Let α be any countable admissible ordinal greater than ω. There is a transitive set A such that A is admissible, locally countable, OnA = α, and A satisfies Σ1-separation. In fact, if B is any nonstandard model of KP + ∀x ⊆ ω (the hyperjump of x exists), the ordinal standard part of B is greater than ω, and every standard ordinal in B is countable in B, then HCB ∩ (standard part of B) satisfies Σ-separation.

It is shown that several natural, undecidable properties of grammars are such that the size of the smallest Turing machine which correctly answers questions of length n grows at a nearly maximal rate as n grows.Thus, in a certain sense, even the finite initial segments of these properties are very complex.In fact, there are natural recursively enumerable properties of grammars such that if it is required that programs run in any fixed recursive time, then the same results hold.The present techniques also enable specific Boolean functionsfn to be exhibited, such that computingfn by a combinational circuit requires a number of gates exponential in the number of inputs tof,.

Abstract Let A be a standard transitive admissible set. Σ1-separation is the principle that whenever X and Y are disjoint Σ1A subsets of A then there is a ⊿1A subset S of A such that X ⊆ S and Y ∩ S = ∅. Theorem. If satisfies Σ-separation, then (1) If 〈Tn∣n < ω) ϵ A is a sequence of trees on ω each of which has at most finitely many infinite paths in A then the function n ↦ (set of infinite paths in A through Tn) is in A. (2) If A is not closed under hyperjump and α = OnA then A has in it a nonstandard model of V = L whose ordinal standard part is α. Theorem. Let α be any countable admissible ordinal greater than ω. Then there is a model of Σ1-separation whose height is α.