Note - Godel's TheoremsThe work of an important, though eccentric, Czech-Austrian mathematical logician, Kurt Gödel (1906-1978) dealt with
completeness and consistency of logical systems. A passing acquaintance with his two theorems would have saved architect a lot of time.
Gödel's First Incompleteness Theorem states that every consistent axiomatic logical system, sufficient to express arithmetic, contains true but unprovable ("not decidable") sentences. In certain cases (when system is omega-consistent), both said sentences and their negation are unprovable. The system is consistent and true - but not "complete" because not all its sentences can be decided as true or false by either being proved or by being refuted.
The Second Incompleteness Theorem is even more earth-shattering. It says that no consistent formal logical system can prove its own consistency. The system may be complete - but then we are unable to show, using its axioms and inference laws, that it is consistent
In other words, a computational system can either be complete and inconsistent - or consistent and incomplete. By trying to construct a system both complete and consistent, a robotics engineer would run afoul of Gödel's theorem.
Note - Turing Machines
In 1936 an American (Alonzo Church) and a Briton (Alan M. Turing) published independently (as is often case in science) basics of a new branch in Mathematics (and logic): computability or recursive functions (later to be developed into Automata Theory).
The authors confined themselves to dealing with computations which involved "effective" or "mechanical" methods for finding results (which could also be expressed as solutions (values) to formulae). These methods were so called because they could, in principle, be performed by simple machines (or human-computers or human-calculators, to use Turing's unfortunate phrases). The emphasis was on finiteness: a finite number of instructions, a finite number of symbols in each instruction, a finite number of steps to result. This is why these methods were usable by humans without aid of an apparatus (with exception of pencil and paper as memory aids). Moreover: no insight or ingenuity were allowed to "interfere" or to be part of solution seeking process.
What Church and Turing did was to construct a set of all functions whose values could be obtained by applying effective or mechanical calculation methods. Turing went further down Church's road and designed "Turing Machine" – a machine which can calculate values of all functions whose values can be found using effective or mechanical methods. Thus, program running TM (=Turing Machine in rest of this text) was really an effective or mechanical method. For initiated readers: Church solved decision-problem for propositional calculus and Turing proved that there is no solution to decision problem relating to predicate calculus. Put more simply, it is possible to "prove" truth value (or theorem status) of an expression in propositional calculus – but not in predicate calculus. Later it was shown that many functions (even in number theory itself) were not recursive, meaning that they could not be solved by a Turing Machine.
