Langston's ant and turmites are two-dimensional analogues of these constructs. Recursively enumerable languages are equivalent to the class of languages recognized by these constructs. The universal v
Langston's ant and turmites are two-dimensional analogues of these constructs. Recursively enumerable languages are equivalent to the class of languages recognized by these constructs. The universal variant of these constructs can simulate every possible one of these constructs. Attaching one of these to an "oracle" can make it stronger, and a busy beaver is a specific variant of these constructs that executes the maximum number of steps. Lambda calculus is equivalent in power to these constructs according to a hypothesis named after Alonzo Church and these devices' namesake. For 10 points, name these theoretical devices with a head that can read, write, and move upon an infinite length of tape.