Alan

A programming language for designing Turing machines.

Walkthrough | Installation | Wiki | Citation

Installation

pip install alan

Walkthrough

This section describes a workflow.

For an in-depth guide navigate to the Wiki. Here are some useful links:

Consider the following example, the definition for a Turing machine that accepts all binary strings that are palindromic:

# This is a definition of a Turing Machine that accepts binary strings that are palindromes
' '
A*
    'X' 'X' < A
    'Y' 'Y' < A
    '0' 'X' > B
    '1' 'Y' > F
    ' ' ' ' > G
B                   # Starting with 0
    '0' '0' > B
    '1' '1' > B
    ' ' ' ' < C
    'X' 'X' < C
    'Y' 'Y' < C
F                   # Starting with 1
    '0' '0' > F
    '1' '1' > F
    ' ' ' ' < E
    'X' 'X' < E
    'Y' 'Y' < E
C
    '0' 'X' < D
    'X' 'X' < D
E
    '1' 'Y' < D
    'Y' 'Y' < D
D
    '0' '0' < D
    '1' '1' < D
    ' ' ' ' > A
    'X' 'X' > A
    'Y' 'Y' > A
G.
    'X' '0' > G
    'Y' '1' > G

Graph the machine:

alan graph examples/binary-palindrome.aln -f assets/readme/binary-palindrome.png

Run the machine on some inputs:

alan run examples/binary-palindrome.aln 101

Accepted
Initial Tape : 101
Final Tape   : 10

alan run examples/binary-palindrome.aln 1010

Rejected
Initial Tape : 1010
Final Tape   : Y010

Animate the computation on some inputs:

alan run examples/binary-palindrome.aln 101 -a -f assets/readme/binary-palindrome-accepted.gif

alan run examples/binary-palindrome.aln 1010 -a -f assets/readme/binary-palindrome-rejected.gif

Citation

If you use this implementation in your work, please cite the following:

@misc{decosta2019alan,
    author = {Kelvin DeCosta},
    title = {Alan},
    year = {2019},
    howpublished = {\url{https://github.com/kelvindecosta/alan}},
}