View source for Descriptions of Turing machines inspired by combinatory logic

{{Template:Foundations infobox}}
__TOC__ 

== Introduction ==

An article on Turing machines, maybe growing to a project to specify (and implement) a general purpose (toy or educational) programming language, that can describe each concrete Turing machine directly: a ''Turing machine definition language''.

Another goal for this article is to show an example of how Haskell (and in general: functional programming) can have an impact on or suggest ideas even in (seemingly) entirely distant, remote areas.

The impact of Haskell to this Turing machine definition language is more than simply using Haskell as an implementation language for this project. The very [[#Syntax|syntax]] of this Turing machine definition language (and its main feature, its [[#Tagging structure|tagging structure]]) comes directly from functional programming languages (Haskell and [[combinatory logic]]).

== Links ==

* [http://en.wikipedia.org/wiki/Turing_machine Wikipedia article]
* [http://www.ams.org/featurecolumn/archive/turing.html Turing machines] page of the American Mathematical Society

== Implementations ==

* Found following links from the previously mentioned AMS site:
** [http://www.nmia.com/~soki/turing/ Virtual Turing Machine (VTM)]
** Paul R. C. Ming's [http://infohost.nmt.edu/~prcm/turing/ Virtual Turing Machine 2 (VTM2)]
* David S. Woodruff's [http://www2.lns.mit.edu/~dsw/turing/turing.html Turing machine interpreter TM]

== Variants ==

There are several variants of defining the concept of a Turing machine. These variants can be classified across several aspects. I shall classify possible variants in terms of two questions:
* how the machine behaves at transitions
* how the the running of the machine terminates
=== A classifying aspect ===

==== Transition ====

I make a distinction between sum-like and product-like transition behavior:
;product-like transition
:means that the head moves ''and'' writes at each transition (this may have a funny consequence: sometimes, we have to undo the last moving step of the head at the end of running -- i.e. there may remain a superfluous last moving that has to be  undone). Maybe that is why some of these variants extend the moving possibilities: besides left, right there is also an idle move.
;sum-like transition
:means that the head moves ''or'' writes at each transition (never both). [Mon:MathLog] describes this approach. I like this approach better, because it looks more economical conceptually (we do not have to undo any superfluous final movings, nor do we need to introduce idle moves) and because it looks nicer for me even conceptually.

==== Halting ====

Halting can be done in several ways -- a (second) special state (final state), or a special action (termination action) etc... Here, I avoid the concept of halting state. The only special state is the starting state, but I do not overload the concept of state in any other way -- halting is achieved in another way

=== A construct called <hask>Maybe2</hask> ===
Sum-like transition and avoiding the concept halting state -- they look like two independent, orthogonal aspects. But a construct (called <hask>Maybe2</hask> in a -- maybe deprecated -- Hugs library module) can implement both aspect in one construct.
<haskell>
 data Maybe2 a b = Nothing2 | Just2 a b
</haskell>
[[Programming guidelines#Types|Programming guidelines]] page recommends to avoid using this construct, and suggests modularizing it to <hask>Maybe (a, b)</hask>. But here I prefer using <hask>Maybe2</hask>, because at this particular problem (defining Turing definition language) this deconstruction pattern does not appear in any other situations, so no redundance is caused by the use of <hask>Maybe2</hask>. And, to tell the truth, I like this construct.

=== Moves ===

There are variants of the Turing machine concept also across other problems,
e.g. how the head and the tape moves related from each other: which is regarded as moving, which is immobile.

Using the facts that
* the head is
** finite (even if the states are included)
** and even limited, even constant (having fixed a concrete Turing machine): it does not grow during a run
* the tape is infinite, or (in some approaches to Turing machine concept) finite but unlimited, maintaining dynamically its appropriate size
I prefer a convention taken from a physical view:
I regard the head as being mobile even if it is made from the heaviest transuranium metal or a black hole, and tape being (or growing) immobile even if it is made of the finest membrane.

== Turing machine definition language as a programming language ==

I use term ''Turing machine definition language'' for what we generally mean when talking on the language of Turing simulator softwares: a language which can represent infinite -- even all possible -- concrete Turing machines, so it is able to serve as an (of course Turing complete, in the most literal meaning) programming language

=== Syntax ===
I was dreaming of a syntax reflecting the conceptual structure of the main concepts -- maybe reflecting even the logic of the Haskell implementation! In general, I do not like special names (like ''<code>start</code> is for starting state, everything else...'') -- I like the concept of ''tag''s much better -- I mean the concept of tags as shown in classical examples -- e.g. direct sum or <hask>Maybe</hask>.

==== Verbose syntax ====

===== Example =====

Incrementing a number represented in the [http://en.wikipedia.org/wiki/Tally_marks tally] (in other words, [http://en.wikipedia.org/wiki/Unary_numeral_system unary]) notation:

 <span style="color:#0b0">starting</span> <span style="color:purple">''':'''</span> <span style="color:blue">blank</span> <span style="color:purple">''':'''</span> <span style="color:red">''Move''</span> <span style="color:brown">right</span> <span style="color:magenta">'''WITH'''</span> <span style="color:#0b0">starting</span><span style="color:orange">;</span>
 <span style="color:#0b0">starting</span> <span style="color:purple">''':'''</span> <span style="color:blue">''Letter''</span> * <span style="color:purple">''':'''</span> <span style="color:red">''Write''</span> <span style="color:blue">''Letter''</span> * <span style="color:magenta">'''WITH'''</span> <span style="color:#0b0">''Becoming''</span> processing<span style="color:orange">;</span>
 <span style="color:#0b0">''Becoming''</span> processing <span style="color:purple">''':'''</span> <span style="color:blue">blank</span>  <span style="color:purple">''':'''</span> <span style="color:red">''Write''</span> <span style="color:blue">''Letter''</span> * <span style="color:magenta">'''WITH'''</span> <span style="color:#0b0">''Becoming''</span> extended<span style="color:orange">;</span>
 <span style="color:#0b0">''Becoming''</span> processing <span style="color:purple">''':'''</span> <span style="color:blue">''Letter''</span> * <span style="color:purple">''':'''</span> <span style="color:red">''Move''</span> <span style="color:brown">right</span> <span style="color:magenta">'''WITH'''</span> <span style="color:#0b0">''Becoming''</span> processing<span style="color:orange">;</span>
 <span style="color:#0b0">''Becoming''</span> extended <span style="color:purple">''':'''</span> <span style="color:blue">blank</span> <span style="color:purple">''':'''</span> <span style="color:magenta">stop</span><span style="color:orange">;</span>
 <span style="color:#0b0">''Becoming''</span> extended <span style="color:purple">''':'''</span> <span style="color:blue">''Letter''</span> * <span style="color:purple">''':'''</span> <span style="color:magenta">stop</span><span style="color:orange">;</span>

==== Tagging structure ====

As we can see, this Turing machine definition language has an algebraically motivated tagging structure. I have taken the idea from Haskell's sum-like datatypes (<hask>Maybe</hask>, <hask>Maybe2</hask>, <hask>Either</hask>) and from the [[Continuation|continuation-passing-style]] implementation of sum-like datatypes ([[Combinatory logic#Direct sum|direct sum]] and [[Combinatory logic#Maybe|Maybe]]) in [[Combinatory logic]] (see also [http://www.madore.org/~david/programs/unlambda/#howto_lists Unlambda's union type]).

This tagging structure makes such programs (i.e Turing machine definitions) more readable, that make use of different namespaces for symbols and states.

As symbols and states are different concept, most Turing machine definition languages allow us to use the same symbol for a state and a symbol -- they are simply in different namespaces. This is a natural consequence of the essential concept of Turing machine. [Mon:MathLog] leverages namespaces in an extreme way: everything -- states, symbols, even actions -- are coded as natural numbers.

The tagging structure enables us also to define the set of states and symbols in an easy way: no burnt-in presupposition is required (e.g. restricting the set of symbols for characters). Special keyword for declaring sets of states and sets of symbols are also superfluous.

==== Algebraic background of the tagging structure ====

Keywords can be classified according their corresponding type and tag coordinates, and coloring scheme can reflect this.

===== Types (represented with colors) =====

;Special keywords
:are common in all Turing machines. They are colored.
;user-given names
:are specific for a concrete Turing machine. They are colorless, more exactly, black in case of light background, and white in case of dark background.

====== States, symbols ======

States and symbols are rather different concepts in the theory of Turing machines, but they both have (maybe incidentally) a common feature. It is worth of distinguishing a special state (the starting state) -- and the same is true at symbols (blank symbol). This has a consequence: the ''tagging structure'' is the same for these two rather different concepts, and this common tagging structure can be covered by <hask>Maybe</hask>.

{| border="1" cellpadding="5" cellspacing="0"
| colspan=2 rowspan = 2 |
! colspan=2 | Tag <hask>Maybe</hask>-like
|-
! style="background:lightgray" | Just
! style="background:lightgray" | Nothing
|-
! rowspan=2 | Concept (type)
! style="background:lightgray" | Symbol
| <span style="color:blue"><code>''Letter''</code></span>
| <span style="color:blue"><code>blank</code></span>
|-
! style="background:lightgray" | State
| <span style="color:#0b0"><code>''Becoming''</code></span>
| <span style="color:#0b0"><code>starting</code></span>
|}

====== Result of transition ======

Representation of halting, and in non-halting cases maintaining new state and action -- this has also a tagging structure. It is <hask>Maybe2</hask>.

{| border="1" cellpadding="5" cellspacing="0"
| colspan=2 rowspan = 2 |
! colspan=2 | Tag <hask>Maybe2</hask>-like
|-
! style="background:lightgray" | Just2
! style="background:lightgray" | Nothing2
|-
! rowspan=2 | Concept (type)
! style="background:lightgray" | Result of transition
| <span style="color:magenta"><code>'''WITH'''</code></span>
| <span style="color:magenta"><code>stop</code></span>
|}

===== Arity (represented with font) =====

The keywords have different arities, and it can be represented with syntax highlighting (by mapping a font type to each arity). But also pure ASCII text can contain this information by appropriate capitalization rules.

;Constant keywords
:are either <hask>Nothing</hask>-like things for special cases (symbol <span style="color:blue"><code>blank</code></span>, state <span style="color:#0b0"><code>starting</code></span>), the <hask>Nothing2</hask>-like solution for halting (<span style="color:magenta">stop</span>), or direction constants like <span style="color:brown">left</span>, <span style="color:brown">right</span>, or user-named things (state or symbol names, varying in each concrete Turing machine). They are typeset with normal font, and it is recommended to type them without any capitals (of course, user-given state and symbol names can ignore this, because state and symbol names are part of the specific Turing machine, so the Turing machine definition language does not restrict their use).
;''Unary'' keywords
:are one-parameter commands like <span style="color:red">''Write''</span>, <span style="color:red">''Move''</span>, or one-parameter state/symbol constructors like <span style="color:#0b0"><code>''Becoming''</code></span>, <span style="color:blue"><code>''Letter''</code></span>. They are typeset with italic, and just the beginning letter is capitalized.
;'''Binary''' keywords
:like <span style="color:magenta"><code>'''WITH'''</code></span>, but considering the idea of currying, the colon sign <span style="color:purple">''':'''</span> is also typeset the same way: they are typeset with bold, and they are either typed with all capitals (<span style="color:magenta"><code>'''WITH'''</code></span>), or they consist of a symbol (<span style="color:purple">''':'''</span>)

==== Concise syntax ====

===== Example =====
 0 : _ : -> / 0
 0 : '* : !'* / @processing
 @processing : _ : !'* / @extended
 @processing : '* : -> / @processing
 @extended : _ : .
 @extended : '* : .

===== Motivation of signs =====
* 0 signing starting state comes from David S. Woodruff's [http://www2.lns.mit.edu/~dsw/turing/turing.html Turing machine interpreter TM]
* Exclamation mark signing the concept of writing comes from the [http://www.comp.lancs.ac.uk/computing/resources/IanS/SE6/IG/Z.pdf Z model-based formal specification language], where exclamation mark is used to mark ''output'' variables
* Repeated colons signing compound cases come from the concept of currying.
* At-character signing state comes from its literal meaning in natural languages (in everyday English language, as a preposition for expressing being at places times or states) -- also reflected in its use in e-mail addresses
* Apostrophe signing a (non-blank) letter comes from using apostrophes in programming languages for character literals and from using apostrophes (or upper corners) for quotations in mathematical logic
* Slash-character signing the concept of ''compound action'' (allowing the possibility of halting instead) comes from the theory of automata
* Dot signing termination is hard to explain. In Prolog, dot is a terminating symbol, but in another sense: it terminates syntactical units (rules and facts), not processes!

=== Examples ===

Let us see some “source code” examples, mainly from [Mon:MathLog].

==== Simple moves ====

<math>T_\leftarrow</math> moves head one cell to the left and <span style="color:magenta">stop</span>s. It is identical to Definition 1.3. of [Mon:MathLog], only the notation is changed:

 <span style="color:#0b0">starting</span> <span style="color:purple">''':'''</span> <span style="color:blue">blank</span> <span style="color:purple">''':'''</span> <span style="color:red">''Move''</span> <span style="color:brown">left</span> <span style="color:magenta">'''WITH'''</span> <span style="color:#0b0">''Becoming''</span> ready<span style="color:orange">;</span>
 <span style="color:#0b0">starting</span> <span style="color:purple">''':'''</span> <span style="color:blue">''Letter''</span> * <span style="color:purple">''':'''</span> <span style="color:red">''Move''</span> <span style="color:brown">left</span> <span style="color:magenta">'''WITH'''</span> <span style="color:#0b0">''Becoming''</span> ready<span style="color:orange">;</span>
 <span style="color:#0b0">''Becoming''</span> ready <span style="color:purple">''':'''</span> <span style="color:blue">blank</span> <span style="color:purple">''':'''</span> <span style="color:magenta">stop</span><span style="color:orange">;</span>
 <span style="color:#0b0">''Becoming''</span> ready <span style="color:purple">''':'''</span> <span style="color:blue">''Letter''</span> * <span style="color:purple">''':'''</span> <span style="color:magenta">stop</span><span style="color:orange">;</span>

<math>T_\rightarrow</math> moves head one cell to the right and <span style="color:magenta">stop</span>s. It is identical to Definition 1.5. of [Mon:MathLog], only the notation is changed:

 <span style="color:#0b0">starting</span> <span style="color:purple">''':'''</span> <span style="color:blue">blank</span> <span style="color:purple">''':'''</span> <span style="color:red">''Move''</span> <span style="color:brown">right</span> <span style="color:magenta">'''WITH'''</span> <span style="color:#0b0">''Becoming''</span> ready<span style="color:orange">;</span>
 <span style="color:#0b0">starting</span> <span style="color:purple">''':'''</span> <span style="color:blue">''Letter''</span> * <span style="color:purple">''':'''</span> <span style="color:red">''Move''</span> <span style="color:brown">right</span> <span style="color:magenta">'''WITH'''</span> <span style="color:#0b0">''Becoming''</span> ready<span style="color:orange">;</span>
 <span style="color:#0b0">''Becoming''</span> ready <span style="color:purple">''':'''</span> <span style="color:blue">blank</span> <span style="color:purple">''':'''</span> <span style="color:magenta">stop</span><span style="color:orange">;</span>
 <span style="color:#0b0">''Becoming''</span> ready <span style="color:purple">''':'''</span> <span style="color:blue">''Letter''</span> * <span style="color:purple">''':'''</span> <span style="color:magenta">stop</span><span style="color:orange">;</span>

==== Simple rewritings ====

<math>T_{\!-}</math> rewrites the actual cell into <code><span style="color:blue">blank</span></code> and stops. Its definition contains a nice trick, that is why it can be more concise than those of <math>T_\leftarrow</math> and <math>T_\rightarrow</math>. It is identical to Definition 1.7. of [Mon:MathLog], only the notation is changed:

 <span style="color:#0b0">starting</span> <span style="color:purple">''':'''</span> <span style="color:blue">blank</span> <span style="color:purple">''':'''</span> <span style="color:magenta">stop</span><span style="color:orange">;</span>
 <span style="color:#0b0">starting</span> <span style="color:purple">''':'''</span> <span style="color:blue">''Letter''</span> * <span style="color:purple">''':'''</span> <span style="color:red">''Write''</span> <span style="color:blue">blank</span> <span style="color:magenta">'''WITH'''</span> <span style="color:#0b0">starting</span><span style="color:orange">;</span>

<math>T_{\!+}</math> rewrites the actual cell into non-blank and <span style="color:magenta">stop</span>s. Its definition is now straightforward (Definition 1.9. of [Mon:MathLog]):

 <span style="color:#0b0">starting</span> <span style="color:purple">''':'''</span> <span style="color:blue">blank</span> <span style="color:purple">''':'''</span> <span style="color:red">''Write''</span> <span style="color:blue">''Letter''</span> * <span style="color:magenta">'''WITH'''</span> <span style="color:#0b0">starting</span><span style="color:orange">;</span>
 <span style="color:#0b0">starting</span> <span style="color:purple">''':'''</span> <span style="color:blue">''Letter''</span> * <span style="color:purple">''':'''</span> <span style="color:magenta">stop</span><span style="color:orange">;</span>

==== Search ====

Let us modularize, decompose the Definition 1.12. of [Mon:MathLog]: let us separate a more simple version!

<math>T_{\leftarrow^*\;0}</math> seeks the first <code><span style="color:blue">blank</span></code> to the left, and it stops if it finds the <code><span style="color:blue">blank</span></code>. We inlude the <span style="color:#0b0">starting</span> in the process of search (i.e. it can stop immediatelly):

 <span style="color:#0b0">starting</span> <span style="color:purple">''':'''</span> <span style="color:blue">blank</span> <span style="color:purple">''':'''</span> <span style="color:magenta">stop</span><span style="color:orange">;</span>
 <span style="color:#0b0">starting</span> <span style="color:purple">''':'''</span> <span style="color:blue">''Letter''</span> * <span style="color:purple">''':'''</span> <span style="color:red">''Move''</span> <span style="color:brown">left</span> <span style="color:magenta">'''WITH'''</span> <span style="color:#0b0">starting</span><span style="color:orange">;</span>

<math>T_{\leftarrow^+\;0}</math> is more complicated. It exludes <span style="color:#0b0">starting</span> from the process of search: it begins with a left move unconditionally. Its definition is identical to Definition 1.12. of [Mon:MathLog] (with changed notation, talky names):

 <span style="color:#0b0">starting</span> <span style="color:purple">''':'''</span> <span style="color:blue">blank</span> <span style="color:purple">''':'''</span> <span style="color:red">''Move''</span> <span style="color:brown">left</span> <span style="color:magenta">'''WITH'''</span> <span style="color:#0b0">''Becoming''</span> searching<span style="color:orange">;</span>
 <span style="color:#0b0">starting</span> <span style="color:purple">''':'''</span> <span style="color:blue">''Letter''</span> * <span style="color:purple">''':'''</span> <span style="color:red">''Move''</span> <span style="color:brown">left</span> <span style="color:magenta">'''WITH'''</span> <span style="color:#0b0">''Becoming''</span> searching<span style="color:orange">;</span>
 <span style="color:#0b0">''Becoming''</span> searching <span style="color:purple">''':'''</span> <span style="color:blue">blank</span> <span style="color:purple">''':'''</span> <span style="color:magenta">stop</span><span style="color:orange">;</span>
 <span style="color:#0b0">''Becoming''</span> searching <span style="color:purple">''':'''</span> <span style="color:blue">''Letter''</span> * <span style="color:purple">''':'''</span> <span style="color:red">''Move''</span> <span style="color:brown">left</span> <span style="color:magenta">'''WITH'''</span> <span style="color:#0b0">''Becoming''</span> searching<span style="color:orange">;</span>

=== Implementation ===

==== Representations of main concepts ====

===== Language =====
<haskell>
 module Language where

 import Util (Maybe2 (Nothing2, Just2))

 type Turing becoming letter = UnsafeTuring (Maybe becoming) (Maybe letter)
 type UnsafeTuring state symbol = state -> symbol -> Maybe2 (Action symbol) state
 data Action symbol = Write symbol | Move Bool
</haskell>

====== Observable non-emptiness: special state, special symbol ======
Most conceptual frameworks of Turing machine concept allow us a big liberty at choosing the set of states and symbols -- but empty set is not allowed. Of course Haskell types are never empty, but non-emptiness provided by <hask>undefined</hask> is not enough. We need discernible, observable non-emptiness. This restriction is reflected directly in the representation of language concepts: we require the presence of a special symbol and a special state.

The trick of <hask>Turing</hask> versus <hask>UnsafeTuring</hask> distinction with <hask>Maybe</hask> solves the problem of special state and symbol. Special symbol is called <span style="color:blue"><code>blank</code></span> and special state is called <span style="color:#0b0"><code>starting</code></span>. The presence of special symbol, special state is reflected directly in the representation of language concepts -- and both are represented by <hask>Nothing</hask>.

This way allows us a big liberty at choosing the set of states and symbols -- we do not have to restrict the user's freedom to use any types for both symbols and states. Strings, integers, enumerations, characters, booleans...
====== Halting ======
Another -- maybe analogous -- problem is the representation of halting.
There may be alternative solutions: introduction of concepts like halting state or halting action, etc... I felt that <hask>Maybe2</hask> (Hugs has this data type in a library module) is a conceptually esthetic solution.

===== Tape =====
At first I wrote a [[Circular programming|circular program]] to make double linked list to implement a Bi-directionally infinite tape. It is superfluous, there is a more simple solution:

<haskell>
 module Tape where

 import Util (Stream (Cons))

 data Tape a = Tp {left, right :: Stream a, cell :: a}
 move :: Bool -> Tape a -> Tape a
 put :: a -> Tape a -> Tape a
 get :: Tape a -> a
</haskell>
...
===== Utility module =====
<haskell>
 module Util where

 data Maybe2 a b = Nothing2 | Just2 a b
 data Stream a = Cons a (Stream a)
</haskell>
=== Extending language ===

A pattern language, or some other extending possibilities, to avoid redundancies. Maybe a macro language as at David S. Woodruff's [http://www2.lns.mit.edu/~dsw/turing/turing.html Turing machine interpreter TM]. Other syntactic sugar.

== Bibliography ==

;<nowiki>[Mon:MathLog]</nowiki>
:Monk, J. Donald: Mathematical Logic. Springer-Verlag, New York * Heidelberg * Berlin, 1976.

[[Category:Theoretical foundations]]