Task: Text Categorization
Input (English): The alternating form of a construct named for him has existential and universal states and is non-deterministic. With an American, he lends his name to a theorem expanded on by Stephen Kleene that concerns the universality of using simple mechanical methods to solve any "effective" problem. One construct proposed by this man comes cannot answer the (*) halting problem and consists of a head reading and writing symbols on a tape. The reverse form of a test named for this man can be demonstrated with CAPTCHAs, although the regular form of that test asks a human to decide if he's speaking to a machine or not. The co-namesake of a theorem with Alonzo Church is, for 10 points, which British computer scientist
Output (English): Science