Bio

Nicholas Ourusoff followed a two-track career as an international programmer-analyst for the United Nations family and a college teacher for several years before choosing to be a college teacher for most of the last twenty years. His academic credentials include an undergraduate degree in Philosophy (Harvard College, 1959), a master’s degree in Computer Science (University of Colorado, 1973), and an interdisciplinary master’s degree in Computer Science and Psychology (New Mexico State University, 1996).

Nicholas enjoys programming and has long-standing interests in computer science, cognitive science and philosophy; in information systems design methodology; and in computing curricula. He has taught mainly at Lander College, Northern Arizona University, and the University of Maine at Augusta, and has also taught or had appointments at the University of Colorado, Lock Haven State College, the University of New Hampshire (College of Lifelong Learning), Lyndon State University, Chancellor College (Malawi), Petrozavodsk State University (Russia), the University of Liverpool, and, starting in the fall of 2004, at Western State College of Colorado. Nicholas’s publications and presentations reflect his interest in teaching and computing curriculum.

He is an avid tennis player, and enjoys Russian language and folk music, hiking, and working in other countries and cultures. Nicholas’s goals include living and working (probably teaching) in other cultures.

Project: Turing Machines with Two States, Two Colors, and a Halting State

This project will enumerate and characterize the approximately 3,000,000 Turing machines (TMs) with two states, two colors, and a Halting state. In addition to enumerating these TMs, the project will identify and group the functions for arbitrary inputs, determining the number of distinct functions and how many of those are partial functions.

Matthew Szudzik has studied TMs with two states and two colors previously, and of the 4096 found 351 distinct functions, 149 of which were total functions.

Turing machines have been important in theoretical computer science ever since Alan Turing introduced them as an abstract machine to make precise what it means to compute. In his A New Kind of Science, Wolfram has studied the simplest TMs in order to answer questions like, “What functions do they compute? Do any manifest complex behavior?” The fact that small TMs–like elementary cellular automata–can be systematically and exhaustively studied is an additional reason to study them.

The characterization of two-state, two-color TMs with a Halting state confirm the results reported by Minsky and Bobrow, namely that all functions show simple behavior. This result is also consistent with earlier systematic NKS work. This study adds detail by characterizing and counting linear and nested functions. For instance, from the 20,736 cases there were 963 distinct functions, about one quarter of which showed nesting.

Favorite Two-Color, Radius-2 Rule

Rule chosen: 1234388462