next up previous
Next: About this document Up: No Title Previous: No Title

Definition of Computerhood (excerpted from p. 477)

Our definiendum will be `x x is a physical computer.' As you can see, we have no trouble whatever defining non-physical (= mathematical) machines; indeed, the definition employs , now the infinite list of all machines in the Arithmetic Hierarchy (the start of the Turing uncomputable portion of AH is easily viewed as a collection of machines). So, the definition employs both the type 3 to type 0 Chomsky Hierarchy, and the Arithmetic Hierarchy For any two machine types T and , we write iff T is less or equal in power to .

(D)
x is a physical computer of type T =


Selmer Bringsjord
Thu Apr 18 11:32:57 EDT 1996