The Cohen-Kung theorem states that a one of these constructs is always unbounded. That entity is Langton's Ant and is one of these constructs on a two dimensional grid. These constructs are equivalent to pushdown automata with two stacks. These entities can interpret all recursively enumerable languages, which are type-0 grammars on the Chomsky hierarchy. The (*) busy beaver function is an uncomputable function about these entities. The creator of these entities demonstrated their equivalence to lambda calculus in a thesis with Alonzo Church. These devices consist of a set of instructions to manipulate ones and zeros on an infinite tape. For ten points, name this model of computation named after a British computer science.
The Cohen-Kung theorem states that a one of these constructs is always unbounded. That entity is Langton's Ant and is one of these constructs on a two dimensional grid. These constructs are equivalent to pushdown automata with two stacks. These entities can interpret all recursively enumerable languages, which are type-0 grammars on the Chomsky hierarchy. The (*) busy beaver function is an uncomputable function about these entities. The creator of these entities demonstrated their equivalence to lambda calculus in a thesis with Alonzo Church. These devices consist of a set of instructions to manipulate ones and zeros on an infinite tape. For ten points, name this model of computation named after a British computer science.
The Cohen-Kung theorem states that a one of these constructs is always unbounded.