248 Are the Androids Dreaming Yet? The story starts back in the 1940s at Berkeley University with a young Julia Robinson, one of the first women to succeed in the previously male-dominated profession of mathematics. By all accounts, she had a wry sense of humor. When asked by her personnel department for a job description she replied: “Monday—tried to prove theorem, Tuesday— tried to prove theorem, Wednesday—tried to prove theorem, Thursday— tried to prove theorem, Friday—theorem false.” Like Andrew Wiles, she fell in love with one of the great mathematical puzzles, and although she made great strides, the problem passed from her to Martin Davis for the next steps. The final elements were put in place in the 1970s with the work of another young mathematician, this time a Russian — Yuri Matiyasevich. Robinson wrote to him when she heard of his proof, “To think all I had to do was to wait for you to be born and grow up so I could fill in the missing piece.” The complete result is the Robinson Davis Matiyasevich theory which sets out the limits of logic and algebra. What, you may ask, do we mean by logic and algebra? Mathematicians like to turn everything into logical statements, even ordering a round of drinks! The discipline of logic emerged from ancient Greece as the study of language. The starting point was the syllogism: Statements such as, “All cows eat grass.” or Lewis Carroll’s assertion, “There are no teachable gorillas.” Over time the study of logic became ever more precise with, for example, the introduction of variables and equations; a=all cows, b=some grass. The formula “a eats b” translates by substitution into, “The cows eat the grass.” This doesn’t look much like a step forward but, trust me, it is. The modern way to represent logic is using prenex normal form. This mouthful simply means separating relationships between things from the things themselves. The following four statements say the same thing, each in a more formalized way. Speech: Harr