Hypercard automata simulation: finite-state, pushdown and Turing machines

ABSTRACT

This paper describes a package of highly interactive simulation models for the concepts taught in Theory of Computing courses. Macintosh Hypercard stacks are used to demonstrate the three basic automata models: Finite-State Machines, Push-Down Machines, and Turing Machines. These simulations feature multiple named machines on the same stack, accessible via a customized menu or buttons on the screen. Because of the scripts hidden behind the visible screen, with just a click of a butto students can alter starting states, the set of input symbols, the number of states, the finality of states, or the action based on a given state/input combination. These simulations have been successfully used in conjunction with a course on the Theory of Computing at Union College since 1989. Students have responded enthusiastically to this concrete method of teaching abstract concepts.

REFERENCES

• 1: [Barwise & Etchemendy] J. Barwise & J. Etchemendy, "Turing's World," Kinko's Academic Courseware Exchange, Santa Barbara, CA, 1986.
• 2: Rick Decker , Stuart Hirshfield, The analytical engine: an introduction to computer science using Hypercard, Wadsworth Publ. Co., Belmont, CA, 1990
• 3: Danny Goodman, Complete HyperCard 2.0 Handbook, Bantam Books, Inc., New York, NY, 1990
• 4: Eitan M. Gurari, An Introduction to the Theory of Computation, W. H. Freeman & Co., New York, NY, 1989
• 5: [Hannay] D.G. Hannay, "Hyper Finite-State Machine," Macintosh Hypercard Forum Library, CompuServe Information Service, 1989.
• 6: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 7: M. C. Lee, An abstract machine simulator, Proceedings of the third international conference on Computer assisted learning, p.129-141, June 1990, Hagen, Germany
• 8: Robert McNaughton, Elementary Computability, Formal Languages and Automata, Prentice Hall PTR, Upper Saddle River, NJ, 1981
• 9: Derrick Wood, Theory of Computation: A Primer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1987

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.3 Applications

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded); Bounded-action devices (e.g., Turing machines, random access machines)

  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.1 Multimedia Information Systems

  K. Computing Milieux
  K.3 COMPUTERS AND EDUCATION
      K.3.2 Computer and Information Science Education
          Subjects: Curriculum

General Terms:
Design, Human Factors, Management