Turing Machines in Flash

I've been writing little flash-based turing machines for a few years, but until now, they have only been available through the Inquiry site interface. Here they are reproduced for common use. All are covered by Creative Commons-share alike license.

Dr. Peter Bradley

Associate Professor of Philosophy
McDaniel College

Director of the First Year Seminar
McDaniel College - Class of 2016

Chair, Philosophy and Religious Studies Department
McDaniel College - Philosophy and McDaniel College - Religious Studies

Office: BMC 110
Hours: TTh 12:40-2:40.

Email: pbradleyATmcdaniel.edu

Specializes in Metaphysics, Philosophy of Mind, Cognitive Science

Links

Peter Bradley at Google
Peter Bradley at G+
Peter Bradley at LinkedIn
Peter Bradley on Facebook
Dr. Peter Bradley at Academia.edu
Peter Bradley at foursquare

Official Stuff

Professional Site
Peter Bradley at McDaniel College Philosophy Department
McDaniel College Philosophy Department

Projects

CT2.0 - Critical Thinking 2.0
The Inquiry Project
Teaching Philosophy Blog
Flash-based Turing Machines
Trends in Philosophy
Simple Flash-based Logic Tools

Personal

Peter Bradley's Web Site
Peter Bradley's Personal Blog
Peter Bradley on Facebook
Peter Bradley on LinkedIn

 Item  MacOSX  WinEXE  HTML  FLA 
 

The Tower of Hanoi show

The classic problem used to demonstrate recursive functions. To solve it, one has to notice that moving X number of blocks, one must move X-1 number of blocks to an 'alternate' post, move the Xth block to the 'target' post and then move X-1 blocks from the alternate post to the target post. Thus, we write a function that calls itself with X-1 blocks and the alternate post as arguments, then moves the Xth block, and calls itself again with X-1 blocks and the alternate post as the 'source' post. If you want to learn more, visit Inquiry: Recursive Functions. hide description
 

Soda Machine

The basic soda machine used to introduce the idea of machine tables. From the description given in Putnam 1967 hide description
 

Machine Table 1

Building the machine table for the soda machine: introductory layout. hide description
 

Machine Table 1b

Building the machine table for the soda machine: 1st step, specify output for $1 input. hide description
 

Machine Table 2

Building the machine table for the soda machine: 2nd step, notice that we need a way of keeping track of an input of 50c. We do so by adding an internal 'state'. hide description
 

Machine Table 3

Building the machine table for the soda machine: specifying the transition to state 2 when input of 50c in state 1. hide description
 

Machine Table 4

Building the machine table for the soda machine: completing the table. State 2 50c input yields soda. State 2 $1 input yields Soda and 50c. Both return to state 1. hide description

Additional Flash-based tools - The actual machines. (1) The shared lib that runs all the TM Machines

 

Turing Machine Shared Lib

This is the shared library for all that follows. It MUST be downloaded and installed in a directory called 'Centre/' for ANY of the following to work. hide description

Additional Flash-based tools - The actual machines. They ALL require the shared LIB!

 

Turing Machine Add

A Turing Machine that will add two numbers together. Numbers are represented by a '0' followed by some number of '1's, so that '011' = 2. hide description
 

Turing Machine Successor

A Turing Machine that will calculate the successor of a number represented by the number of 1s following a 0 (i.e. 011 = 2) in a new location on the tape. From Kleene, 1967. hide description

Additional Flash-based tools - The Universal machines. They ALL require the shared LIB!

 

Turing Machine Binary Count

A Turing Machine that 'count' in binary. That is, it will write the binary numbers in sequence on the tape, and return to the leftmost square on the tape when each number is completed. Notice: the machine writes the numbers backwards, so '01' = '10' and '001' = '100'. Machine specification from Minsky, 1967, p 137-154. hide description
 

Turing Machine Universal Setup 1

Building the universal machine: extend the tape infinitely to the left to hold the instructions, and mark the 'middle' point with a 'Y'. Designate the two squares immediately to the left of the 'Y' to hold the current state of the machine and the last number read from the tape. Machine specification from Minsky, 1967, p 137-154. hide description
 

Turing Machine Universal Setup 2

Building the universal machine: specify the starting condition for this tape: state 0, last symbol read '1'. Machine specification from Minsky, 1967, p 137-154 hide description
 

Turing Machine Universal

The working universal machine. The instructions are loaded onto the tape from right to left in to the left of the last-number-read block. The computational area is marked off with an 'M'. If you are interested, there is a description of how we encoded the machine table into binary as well the states the universal machine goes through at the Inquiry project: Universal Turing Machines. Machine specification from Minsky, 1967, p 137-154. hide description

Additional Flash-based tools - The Natural Language machines. These do NOT require the shared lib

 

Turing Machine Natural Language 1

Inspired by a illustrative example used by Pinker in his 1995 book The Language Instinct, I decided to create a Turing machine to implement the English question-form based on verb-movement: we can turn a declarative sentence like "The rose is in the vase" into a question by moving the verb to the front of the sentence: "Is the rose in the vase?" This machine takes words as its inputs, matches them to a database of known words categorized as grammatical parts of speech, and then uses those classifications to execute actions according to its machine table. Can you create a sentence that it cannot parse correctly? hide description
 

Turing Machine Natural Language 2

There are a number of ways in which the last will fail, the most obvious of which is its inability to handle verb or noun phrases. This one, which contains in internal 'template' of the structure of grammar (i.e. Chomsky) handles these better. Can you break it now? hide description
 

Turing Machine Natural Language 3

The last one couldn't handle clauses: it would turn the sentence "The rose that is in the vase is on the table" into "Is the rose that in the vase is on the table", a mistake that Chomskians tell us a normal human would never make. This machine handles clauses by blocking them off an inserting them in at the end. hide description
 

Turing Machine Natural Language - recursive

This final machine handles clauses correctly: as mini-sentences. Thus, when it hits a clause, it starts its processing over, creating a new grammatical tree. Now: Can you break it? hide description

Additional Resources

The flash movies above are embedded into modules that are distributed via the 'mind project'. If you would like to read a 'textbook' introduction to Turing machines:

Introduction to symbolic models
  1. Recursive Functions
  2. Introduction to Machine Tables
  3. Turing Machines
  4. Universal Turing Machines
  5. Turing Machines and the Natural Language
  6. The Turing Test

Works Cited:

Putnam, Hilary. (1960). "Minds and Machines". Reprinted in Putnam (1975) Mind, Language, and Reality. Cambridge: CUP.

Minsky 1967 Computation: finite and infinite machines Upper Saddle River, NJ: Prentice Hall

Kleene 1967 Mathematical Logic New York: Wiley

Pinker 1995 The Language Instinct: How the Mind Creates Language. Harper Perennial Modern Classics