SiNo: Uma ferramenta didática de apoio para o ensino de máquina NORMA

Abstract

The theory of computation, as we know it today, began to flourish as an independent research field in the early 1900s. One of its main enablers was David Hilbert’s famous Entscheidungsproblem, a mathematical problem in logic that can be phrased as the following question: is there an effective method that can determine, in a finite amount of steps, the validity of a given formula expressed in the language of first-order arithmetic? In an effort to solve Hilbert’s Entscheidungsproblem, a group of mathematicians and logicians (most notably Alonzo Church, Alan Turing, Kurt Goedel, Emil Post and Stephen Kleene), throughout the 1920s and 1930s, set out to find a precise, rigorous definition of the intuitive notion of "effective method". As a result of their work, different (but equivalent) formal models of computation were proposed, such as Turing machines, the untyped 𝜆-Calculus and the general recursive functions. Later on, in the 1960s and 1970s, another strand of models of computation was introduced in the literature, namely the unlimited register machines. The NORMA machine (Number-theORetic Register MAchine), a very minimalistic kind of unlimited register machine, was invented by Richard Bird in 1976. In this work, we present SiNo, a user-friendly simulator for the NORMA machine. We hope that this simulator can be used as a didactic tool to help teachers communicate, in a clearer and more straightforward manner, abstract concepts within the scope of the theory of computation. There are some other NORMA machine simulators available on the Internet. However, what distinguises ours from those is that our simulator has a more flexible syntax, which makes the learning experience less tedious. We have built SiNo using the Python programming language and following the well-known waterfall model of software engineering. During the development of our work, we had the opportunity to employ SiNo in classroom activities and to get positive feedback from students.