Abstract:

The recent film "The Imitation Game" has brought back the debate as to whether a computer could think. But from the educational point of view, some fundamental understanding is necessary for our ICT graduates to be informed participants in the debate. The challenge is how to teach what is a Universal Turing Machine (UTM) to a generation mostly unaware of mechanical devices. Typewriter became completely non-existent in the West at the turn of the century. Mechanical calculators and the slide rule disappeared from main use by the end of the 1970. Thus, how is it possible that a single-tape abstract model like an UTM be as "powerful" as the sophisticated game-boxes, watches, smart phones, and monstrous parallel computers that youngsters entering university experience today for e-mailing, networking, and tele-conferencing. Besides, many are familiar with other capacities of computers that display intelligence. Can the current generation of university students become convinced of the equivalence of our modern computers to such an abstract model? How can we teach such equivalence? We claim we inculcate a reflective stance on information technology and discuss professional issues in IT using this equivalence-of-power concept as the starting point.

In our Foundations of Computing course, the aim is not only to teach some general aspects of how computers work (like binary notation), but also to enable students to truly comprehend the notions of algorithm, technology, and even the notion of information to be able to exercise professional judgment. A fundamental exercise in the course is being able to convincingly understand and reproduce the UTM argument. At least, so we know that there are problems (like the Halting problem) our current computers cannot solve.

We use a series of simulators that provide clear illustrations of how a computer works, commencing from very basic logic gates of hardware. Modulo miniaturization, students can comprehend how and adder is built and how an arithmetic logic-unit is built. Eventually, a simulator of a simple von Neumann architecture is used to develop some simple programs. This achieves a concrete experience of the notion of stored-program, significantly close to the notion of UTM. But how is this a machine that moves from states into states? A simulator of a Turing Machine (TM) is used to build simple programs, programs that become progressively more elaborate, from adding two numbers, or multiplying two numbers, to actually verifying that the input is the description of another machine.

The fact that the TM simulator is coded in java is enough to establish that anything a TM can compute, java can compute. The challenge is the other way around. For this, we develop more concrete constructions of the power of a TM. For example, that a TM in binary or one that can store hexadecimal symbols in each of its cells are computationally equivalent. We reach a point that the TM behavior and actions are very much the simulator of the von Neumann Machine describing the modern CPU. Therefore, a TM can emulate anything executable in a modern stored-program CPU. This exercise not only has the computability implications but also enables to represent other many issues of current computer systems, like virtualization, viruses or computation in the cloud. More importantly, we can enter the philosophical argument of whether machines understand what they are doing, and in that regard whether they would be able to think.

Keywords:

Concrete vs Abstract Concepts, Students Experiences, Debate on the power of thinking machines.