250 Are the Androids Dreaming Yet? algorithm, but a VAV, (for all, there exists, for all), is not. Each individual type of problem within the class must be examined with insight and understanding. Our lives are full of problems — playing chess, finding a mate, designing space ships and simply getting to work in the morning. Imagine we expressed everyday problems as logical problems. Where is the logic limit for life? We have no answer for this yet, but we do know the logic limit for computing; it is given by Rice’s Theorem. Named after Henry Rice, and proven in 1951 as part of his doctoral thesis at Syracuse University, Rice’s Theorem states: “No nontrivial feature of a computer program can be automatically derived” You cannot tell if a program will halt with a given input. You cannot tell if one program will generate the same output as another. You cannot tell if a simpler program could be written to do the same task as a more complex one. In fact, no nontrivial thing can be proven. This means the logic limit in computers is low, and computer programmers have job security. For Programmers For the programmers amongst you, here are some of the things that cannot be done automatically even given infinite time: « Self-halting Problem. Given a program that takes one input, does it terminate when given itself as input? ¢ Totality Problem. Given a program that takes one input, does it halt on all inputs? * Program Equivalence Problem. Given two programs that take one input each, do they produce the same result on every input? * Dead Code Elimination. Will a particular piece of code ever be executed? e Variable Initialization. Is a variable initialized before it is first referenced? * Memory Management. Will a variable ever be referenced again? HOUSE_OVERSIGHT_015940