INSTRUCTIONAL SOFTWARE FOR THE THEORY OF COMPUTATION

M.A.Alberti [1]

ABSTRACT

A software environment where it is possible to simulate different abstract models of computation is described. The users are students enrolled in a Computer Science program and applications are aimed at teaching rudiments of theory of computation in a friendly way. So far applications consist of three different modules to simulate finite state automata, Turing machines and neural nets. They have been developed in the project COnceptual Learning Of Science (COLOS), a COMETT project, and are highly based on graphical interaction with the computer. They run on a HP 9000/360, under RMG, a tool kit for authoring visualization courseware developed at the Hewlett-Packard laboratories. RMG supports an incremental style of programming, being embedded in an object oriented environment. The applications as well as RMG are written in Objective-C.

INTRODUCTION

The applications described hereafter are part of a project to develop instructional software to help students, even with little computer science background, to master fundamental ideas of abstract computer theory in a friendly and exploratory way. This project is part of an European project called Conceptual Learning of Science, which aims at exploring the potential of powerful computer graphics as a mean of conveying information and concepts to enhance qualitative understanding in science. In the learning process often we see that mathematics and formal methods can, at the first stage, both become an obstacle in itself, and divert from understanding basic concepts. Moreover the first impact can shape students' attitude to a subject and therefore it should be a time to offer an opportunity for developing intuition and clear images about what it is involved. Formal insights into the subject can be reached at the second stage, after some intuitive understanding and motivation in further learning are gained. In the study of the theory of computation, students are often required to deal with abstract computation devices that are formally defined and that, for this reason are far from, students' experience. Whereas willingness to experiment and explore are confined to real computers, abstract models of computation are perceived as "abstract" and not worth trying to work out experiments. Applications described here are a first step towards the design of an environment where it is possible to experiment and feel the concreteness of different abstract models of computation. It should provide a bridge between intuition and formal theories, something to play with and to explore.

Applications consist of three different modules to simulate finite state automata, Turing machines and neural nets. The first two modules allow students to confront the concept of a finite automata or a Turing machine, to try out examples, to look at them while the computation is carried out; the neural nets module introduces students to different models of neuron, allowing them to build different net architectures and to watch their behaviors.

An instance of any model, automaton or Turing machine, is defined by giving the state diagram; this allows the students to define the computation device in a constructive way, modelling it interactively. The simulation gives a sense of the computation that is being done and can be used both to understand a given automaton or Turing machine and to give feedback during the design phase. As for neural nets, a particular net is also defined by giving its diagram, where each node is a neuron of a chosen kind, and where arcs in and out of a node correspond to input and output of a neuron.

USER INTERFACE

The user interface is the same for all modules. An application is shown in a window that can be displayed in a chosen position on the screen. Different windows can be opened at the same time; they can have any size and whatever is shown in it can be zoomed in and out or can be scrolled in any direction.

The interaction is mostly graphic, since the input to each computing device is given by the state diagram, and therefore each module provides a graphic editor to define the model: displaying nodes and arcs in a desired layout. All modules are provided with documentation on line about how to use the simulation and with a text editor to write notes and comments about what the user is doing.

In each module predefined examples can be displayed and run. Simulations can be executed in two modes: step by step or in a continuous mode at a chosen velocity. Each example is associated to some text to explain what the model does or to give comments and information.

If a conceptual error can be detected, a special button highlights. To provide feedback error messages can be displayed clicking the button. Displaying messages only on request has been implemented in order to avoid boring error messages in those cases in which a simple reminder can be already enough. The idea is that feedback should occur immediately after the error is detected but should not distract from what one is doing.

MODULE ON NEURAL NETS

The neural net module is a general purpose simulator that can be used to design and explore different connectionist architectures: namely binary threshold neuron networks, Hopfield nets and Boltzmann machines [1].

The net is defined by choosing a model for formal neurons, namely the nodes, setting the connections between nodes and their weights and choosing a dynamic for the net. The neuron model is defined by giving the input, the output, the state space, a transition function and a threshold. The inputs simulate the signals travelling along the connections; the output is always the state as computed by the transition functions. The choice in setting the transition function is between a probabilistic and a deterministic one. In both cases several functions are found in the literature and some of them are implemented in the simulation, such as the Heavy-side function or the Hinton-Sejnowski-Ackley one. All the nodes in a net are of the same model. We may choose some nodes as input nodes; thereafter, their states do not change during the simulation.

At the net level the connections among neurons are defined, either mono or bi-directional. Their weights are also defined and then a net neurodynamic, which could be probabilistic sequential or parallel, is chosen.

The simulation gives an experimental environment, that will be enriched adding learning algorithms, where one can analyse the behavior of a given net.

MODULE ON FINITE STATE AUTOMATA

In this module a deterministic finite automaton is defined by giving an alphabet and the state diagram: displaying graphically the nodes, the arcs and their labels, and choosing initial and final nodes. Then an input string can be given interactively and the simulation run, telling if the input string has been accepted or not, since the automaton acts as a language recognizer.

To fill the gap between graphic animation at simulation stage and formal automaton definition, for each example its definition as a quintuple, can be displayed on demand and state transition function can be examined during the simulation. Moreover the grammar equivalent to the automaton can be shown. A future development will be to derive automatically the language defined by this grammar. So that a student could give a string from the language as input to the automaton and could verify that it is accepted, showing the equivalence between the two representations.

Non deterministic finite automata will also be implemented and their relations with regular languages will be stressed.

MODULE ON TURING MACHINES

The module is similar to the finite automata one: whereas a finite automaton is a language recognizer and it does not deliver any output except for an indication whether or not the string on the input tape is accepted, the Turing machine carries on a computation. In fact it can, not only read but also write characters on the input tape and at each state it decides whether to move right or left on the input tape.

The Turing machine is defined giving its diagram: the states and the arcs, with an associated triple, consisting of the read symbol, the output symbol and the action (scanning next cell right or left on the tape). A formal definition of the machine as a tuple is given on demand. The tape extends indefinitely to both ends.

Moreover the machine can be decomposed into sub-machines, associated to a node of the diagram. This features allows users to build upon previously defined examples, in order to design machines to perform more complex tasks, that show modularity. A formal treatment about how to combine Turing machines can be found in [2].

A further development will be a simulation for two tapes Turing machines.

RMG ENVIRONMENT

RMG provides a rich programming environment with powerful graphic capabilities [3]. All features of user interface are implemented by RMG; namely: the window, in which an application is shown; how to size it, how to move it; how to scroll and zoom what it displays and so on. In RMG any application is a different window, where very diverse programs can be run: simulations, text editors, or browsers.

Being designed as an object oriented environment, based on Objective_C under UNIX, RMG allows to write applications from scratch or modifying the existing ones. Inheritance property of that object-oriented language allows to use classes and objects of existing applications and to create new ones as an extension of previous ones. These program design aspects in an object oriented environment are discussed in [4].

RMG provides several development tools: browsers for classes; text and icon editors; to create windows; to create pop up menus; to monitor variable evolutions at run time and to graph or visualize quantities and so on. It offers authoring facilities, especially interesting for simulations of physical phenomena, that require graphic and animation.

ACKNOWLEDGEMENTS

I would like to acknowledge the contribution of people who actually implemented applications: M.P. Pensini wrote the neural net module; R. Migliorini and M.Scagliotti wrote the automata module and Turing machine one respectively, as part of their thesis work.

REFERENCES

1. M.A.Arbib Brains, Machines, and Mathematics (Springer-Verlag, New York) 1987

2. H.Lewis, C.Papadimitriou Elements of the Theory of Computation (Prentice-Hall, Englewood Cliffs, NJ, USA) 1981

3. Z.Fazarinc RMG user's first aid kit (Hewlett-Packard Co., Palo Alto, CA USA) June 1989

4. M.A.Alberti, R.Migliorini, M.Scagliotti An application of Object Oriented Programming to the development of learning environments, submitted to ICCAL '90