Christopher DuPuis
Oregon State University |
Margaret Burnett
Oregon State University |

Department of Computer Science

Oregon State University

Corvallis, OR 97331

July 1997

In discussing the functionality of a programming language, it is
useful to determine whether the computational power of the language is
equivalent to general purpose languages such as C, Lisp, and Java; or if
its application is necessarily limited to special purposes, as are such
languages as Microsoft Excel^{®} and SQL [Kiper et al 1997].
This determination can be made by demonstrating whether or not a language is
Turing complete. Turing completeness implies that any computation that can
be performed in the language can be performed on a Turing machine and vice
versa. According to the Turing Thesis, any problem that is computable
by any machine can be solved using a Turing machine [Linz 1996].
Thus, to show that a language
is Turing complete, it is necessary to show only that the language has no
less computational power than a Turing machine.

Although commercial spreadsheet languages are not Turing complete, it is possible for a language using the spreadsheet programming paradigm to be Turing complete. One example is the spreadsheet-based visual programming language (VPL) Forms/3. This paper demonstrates Forms/3's Turing completeness with the following implementation of a Turing machine simulator.

As mentioned, programming in Forms/3 follows the spreadsheet paradigm, in that the programmer creates cells on a form, and then enters formulas into each of these cells. Because Forms/3 follows lazy evaluation rules, only those cells whose values are required in order to display correct values for any visible cells will be evaluated at a given time. Also, rather than defining an atomic value for the cell, a formula defines a temporal vector, which is a series of values taken by the cell over the course of logical time [Burnett and Ambler 1994]. In Forms/3, logical time is the language-defined dimension that is used to maintain distinct and synchronized values for every cell in a program. Because of these temporal vectors, Forms/3 is able to maintain referential transparency, even to the extent that time-based programs can run both forward and backward through logical time. Formulas can refer to the values of other cells, both at the current logical time and at earlier times. The operations that are used in this example are described here. See [Hays and Burnett 1995] for a more complete introduction.

*if/then/else*- The conditional expression is analogous to the Lisp
"
`(if test thenClause elseClause)`

," and allows nesting in exactly the same manner. It returns the result of the*then*clause if the test is true, otherwise it returns the result of the*else*clause. In Forms/3, the*else*clause is optional, and the failure of the test in an*if/then*expression results in no new value being defined. *earlier/initially/until*- The
*earlier*expression provides reference to the value of a cell during the previous moment of logical time, thus allowing non-destructive iteration. The optional*initially*modifier allows the programmer to define a value for the cell at starting time, and the*until*modifier allows the programmer to specify that, when the test in the*until*clause becomes true, the cell's value applies for all future moments in time. For example, if a cell named "`foo`

" has the formula: "`earlier (foo + 1) initially 1 until (foo > 5)`

," it would count from 1 to 6, and its value at all later times would be 6. *fby**Fby*specifies an initial value for a cell and its value after a start time. For example, "`1 fby 2`

" would define a cell as having the value 1 at time 1, followed by the value 2 at all later times.*matrixSearchRowWhere*and*matrixSearchColWhere*- These expressions allow the programmer to search through a matrix for a specific value. If it is found, its row or column is returned.
*error?*- This expression returns TRUE for values of type error, and FALSE otherwise.
**Matrix access**- Matrices are accessed using the syntax "
`aMatrix[row@col]`

," where`aMatrix`

is the name of the matrix, which is indexed by the values of`row`

and`col`

. The values of`row`

and`col`

can be integers or cell names. It is also possible to specify "`aMatrix[i@j]`

," which is the element of`aMatrix`

that has the same row and column indices as the referring cell. Here,`i`

and`j`

are reserved words.

This Turing machine simulator includes three separate forms in its program: The form TuringProgram (Figure 1) contains all of the user-modifiable cells that define the properties of the Turing machine to be modeled. The form TuringCompute (Figure 2) carries out the operations which translate the Turing machine definition in TuringProgram into behaviors of TuringInterface (Figures 3, 4, and 5). The form TuringInterface has a matrix for user input, as well as an animated display of the machine tape.

This demonstration Turing machine is programmed (via TuringProgram in Figure 1) to take a string of binary digits as its input, and the result is that string concatenated with itself. That is, it performs the computation:

for any string

where

Its method of carrying out this program can be summarized as follows:

- Traverse the original string from left to right, replacing each "0" with an "x" and each "1" with a "y".
- Return to the left end of the string, and replace the first letter with its corresponding numeral.
- Move to the first blank to the right of the string, and write the same numeral as written in step 2.
- Repeat from step 2, until only numerals are present in the final string.

*Figure 1: TuringProgram defines the transitions, states, and tape
symbols used by the simulator.
In the *Transitions* matrix, the first row is the index of tape
symbols, and the first column is the index of states. The proper transition
is found by accessing the matrix element found in the row containing the
current state as its index, and in the column containing the current tape
symbol. The transitions are expressed as triples, consisting of the
next state, the symbol to write on the tape, and a direction to move.
Every cell on this sheet (except *RealInitialTapePosition*) is
meant to be edited by the user to change the program given to the
Turing machine. Thus, all of these cells have constant formulas (e.g. "3").
*RealInitialTapePosition* is an interface convenience, which is meant
to hide the fact that the actual operation of the Turing machine places
a "Blank" in the first *Tape* position.*

*Figure 2: TuringCompute performs calculations necessary to operate the
interface. *CurrentGlyph* is the graphic that is used as a pointer in the
animation, and its appearance depends on whether or not the
calculation is finished.*

*Figure 3: TuringInterface: initial state of the interface, showing the
calculations used to display the tape and the animation. The *
Input* matrix can be modified by the user. All cells are
shown, and the *Tape* and *Indicator* matrices have been
moved farther apart than normal to allow room for displaying all formulas.*

*Figure 4: TuringInterface: the interface as seen by the user, at an
intermediate stage of calculation. While Figure 3 showed all of the
implementation details of this form, this figure shows only the features
visible to the user. The cell *lessCols* and the matrix *Helper
* have been hidden, as have the formula tabs for everything and the
borders and labels for the *Tape* and *Indicator* matrices.*

*Figure 5: TuringInterface: final state of the interface.*

This demonstration shows that the VPL Forms/3 can simulate the operation of a Turing Machine. Therefore, Forms/3 has computational power equivalent to that of a Turing machine.

- Burnett, M. and A. Ambler (1994), "Interactive Visual Data Abstraction
in a Declarative Visual Programming Language",
*Journal of Visual Languages and Computing*, 29-60, March 1994. - Hays, J. and M. Burnett (1995), "A Guided Tour of Forms/3", TR 95-60-6, Oregon State University Computer Science Dept., June 1995.
- Kiper, J., E. Howard, and C. Ames (1997), "Criteria for Evaluation
of Visual
Programming Languages",
*Journal of Visual Languages and Computing***8**, 175-192. - Linz, P. (1996),
*An Introduction to Formal Languages and Automata*, Second Edition, D.C. Heath and Co., 1996.