Turing Machine in C#

Question

I've tried designing a Turing Machine model, it works quite well, however I think it could be confusing to maintain on in the future, and I'm not sure what of best practices. Can I get some feedback on my code?

Turing Machine Namespace

using System;
using System.Collections.Generic;

namespace TuringMachineNS
{
    public class TuringMachine
    {
        byte[] tape;
        public bool hasTerminated;
        int currentIndex;
        int currentCard;
        List<ControlCard> cards;

        public TuringMachine() : this(500) { }

        public TuringMachine(int size) : this(size, null) { }

        public TuringMachine(int size, List<ControlCard> cards)
        {
            this.hasTerminated = false;
            this.tape = new byte[size];
            this.currentIndex = tape.Length / 2;
            this.cards = cards;
            this.currentCard = 1;
        }

        public void NextInstruction()
        {
            if (this.currentCard == 0)
            {
                hasTerminated = true;
                return;
            }
            if (this.currentIndex > this.tape.Length || this.currentIndex < 0)
            {
                hasTerminated = true;
                return;
            }
            int value = this.tape[this.currentIndex];
            Instruction Inst = this.cards[this.currentCard].GetInstruction(value);
            this.ExecuteInstruction(Inst);
        }

        private void ExecuteInstruction(Instruction inst)
        {
            if (inst.ActionInst == RWInstructions.WRITE0)
            {
                this.tape[currentIndex] = 0;
            }
            else if (inst.ActionInst == RWInstructions.WRITE1)
            {
                this.tape[currentIndex] = 1;
            }

            if (inst.MovementInst == LRInstructions.MOVELEFT)
            {
                this.currentIndex--;
            }
            else if(inst.MovementInst == LRInstructions.MOVERIGHT)
            {
                this.currentIndex++;
            }

            this.currentCard = inst.NextCardToUse;
        }

        public override string ToString()
        {
            string tapeString = "";
            foreach (var item in this.tape)
            {
                tapeString += item;
            }
            string secondLine = "";
            for (int i = 0; i < this.currentIndex; i++)
            {
                secondLine += " ";
            }
            secondLine += "^";
            return $"{tapeString}\n{secondLine}\n";
        }
    }

    public class ControlCard
    {
        Instruction IfZero;
        Instruction IfOne;

        public ControlCard(Instruction zero, Instruction one)
        {
            this.IfZero = zero;
            this.IfOne = one;
        }

        public Instruction GetInstruction(int value)
        {
            return value == 0 ? this.IfZero : this.IfOne;
        }
    }

    public struct Instruction
    {
        public RWInstructions ActionInst;
        public LRInstructions MovementInst;
        public int NextCardToUse;
    }

    public enum RWInstructions
    {
        WRITE1,
        WRITE0,
        UNCHANGED
    }

    public enum LRInstructions
    {
        MOVERIGHT,
        MOVELEFT,
        DONOTMOVE
    }
}

Example Usage

using System;
using System.Collections.Generic;
using TuringMachineNS;

class Program
    {
        static void Main(string[] args)
        {
            Instruction instr0 = default(Instruction);
            instr0.ActionInst = RWInstructions.WRITE1;
            instr0.MovementInst = LRInstructions.MOVELEFT;
            instr0.NextCardToUse = 1;
            Instruction inst1 = default(Instruction);
            ControlCard controlCard = new ControlCard(instr0, inst1);
            List<ControlCard> cardsList = new List<ControlCard>() { null, controlCard };
            TuringMachine tm = new TuringMachine(20, cardsList);
            Console.WriteLine(tm);
            while(!tm.hasTerminated)
            {
                tm.NextInstruction();
                Console.WriteLine(tm);
            }

        }
    }

Example Output

00000000000000000000
          ^

00000000001000000000
         ^

00000000011000000000
        ^

00000000111000000000
       ^

00000001111000000000
      ^

00000011111000000000
     ^

00000111111000000000
    ^

00001111111000000000
   ^

00011111111000000000
  ^

00111111111000000000
 ^

01111111111000000000
^

11111111111000000000
^

11111111111000000000
^

Answer 1

I would store the value to write directly in the Instruction. That way you don't need the if-else in ExecuteInstruction. Instead it's just an assignment.

this.tape[currentIndex] = inst.ValueToWrite;

I would also store the NextCard value directly. This requires ControlCard to be a reference type but that's already the case. You do need to pass which state is the final state.

It is very likely that the tape would need to grow. If the tape can't grow then you technically don't have a turing machine.

Also it may be handy to be able to initialize the state of the tape before starting.

Answer 2

I don't think you should have constructors that don't take a List<ControlCard> as parameter. It doesn't have any value since this way the TuringMachine won't be able to operate. If I want a machine that'll execute 0 operations, I'll pass an empty List<ControlCard>.

You should specify visibility modifier for your class members, at least I think. We could argue that since the default value is private and that considering OOP members should always be private this wouldn't matter, but I think it would add to the readability!

In your ToString() method you could use string tapeString = String.Join("",tape) instead of

string tapeString = "";
foreach (var item in this.tape)
{
    tapeString += item;
}

Answer 3

• Remove the extra this. whenever it isn't required. It makes your code cleaner and anyone writing in a good IDE can put their mouse over the variable to see where it's coming from, they don't need you to prefix every var with this.
• Use the var keyword to avoid declaring types when possible. This makes it easier to change your mind on types later and it helps your declaration lines line up. Keeps code DRY.
• Drop the Inst suffix on Action and Movement since you're already in an Instruction. It's redundant.

Here's my suggestions in action, along with a few other improvements.

using System;
using System.Collections.Generic;

namespace TuringMachineNS
{
    public class TuringMachine
    {
        byte[] tape;
        public bool hasTerminated;
        int currentIndex;
        int currentCard;
        List<ControlCard> cards;

        // Added "= null" to make cards optional, can eliminate other constructors
        public TuringMachine(int size, List<ControlCard> cards = null)
        {
            hasTerminated = false;
            tape = new byte[size];
            currentIndex = tape.Length / 2;

            // Null coalescing operator '??' will create empty list if needed.
            this.cards = cards ?? new List<ControlCard>();

            currentCard = 1;
        }

        public void NextInstruction()
        {
            // Combined both if statements into one since they lead to the same code. No performance hit due to 
            // short-cicuit evaluation.
            if ((currentCard == 0) || (currentIndex > tape.Length || currentIndex < 0))
            {
                hasTerminated = true;
                return;
            }

            var value = tape[currentIndex];
            var Inst = cards[currentCard].GetInstruction(value);
            ExecuteInstruction(Inst);
        }

        private void ExecuteInstruction(Instruction inst)
        {
            if (inst.Action == RWInstructions.WRITE0)
            {
                tape[currentIndex] = 0;
            }
            else if (inst.Action == RWInstructions.WRITE1)
            {
                tape[currentIndex] = 1;
            }

            if (inst.Movement == LRInstructions.MOVELEFT)
            {
                currentIndex--;
            }
            else if(inst.Movement == LRInstructions.MOVERIGHT)
            {
                currentIndex++;
            }

            currentCard = inst.NextCard;
        }

        public override string ToString()
        {
            var tapeString = string.Join("",tape);
            var secondLine = "";
            for (int i = 0; i < this.currentIndex; i++)
            {
                secondLine += " ";
            }
            secondLine += "^";
            return $"{tapeString}\n{secondLine}\n";
        }
    }

    public class ControlCard
    {
        // Combined instructions into array. Equivalent code but allows for expansion. A dictionary
        // could also work well here if you want to allow arbitrary characters.
        Instruction[] Instructions;

        public ControlCard(Instruction zero, Instruction one)
        {
            Instructions = new Instruction[] { zero, one };
        }

        public Instruction GetInstruction(int value)
        {
            if (value == 0 || value == 1)
            {
                return Instructions[value];
            }
            else
            {
                // Throw an exception if value isn't zero or one
                throw new ArgumentOutOfRangeException("value", value, "value argument must be zero or one.");
            }
        }
    }

    public struct Instruction
    {
        // Dropped Inst suffix. You are already in an instruction object, 
        public RWInstructions Action;
        public LRInstructions Movement;
        public int NextCard;
    }

    public enum RWInstructions
    {
        WRITE1,
        WRITE0,
        UNCHANGED
    }

    public enum LRInstructions
    {
        MOVERIGHT,
        MOVELEFT,
        DONOTMOVE
    }
}

Answer 4

Review

• hasTerminated should be a public property with private setter and be renamed Terminated.
• TuringMachine could be a sealed class so you don't need to worry about which private data should actually be protected and which methods virtual.
• List<ControlCard> cards should be IEnumerable<ControlCard> since you do not add/remove elements from it.
• Check all input arguments on public entrypoints of your classes against null.
• NextInstruction is a bit of a black-box. Have it return a bool returning true as long a next card is available and not terminated.
• The this keyword is redundant because there are no naming conflicts between local and instance variables.
• The early exit conditions in NextInstruction can be combined in a single statement. However, I feel the second condition should throw an ArgumentOutOfBoundsException instead and the instance should guard against letting currentIndex getting out of bounds.
• ExecuteInstruction should execute the instruction and nothing more. this.currentCard = inst.NextCardToUse; should be called by its container method NextInstruction.
• Some people have argued that Instruction should hold the state to set in order to mitigate if statements in the machine. If you do this, then also use a Func<int, int> to handle LRInstructions without using an if statement. For instance, LRInstructions.MOVELEFT would yield (i) => i--;. But I would keep the if statements since handling the instructions is part of the machine, not the Instruction. An instruction is just a triggered event, nothing more.
• ToString should use a StringBuilder instead of a string tapeString.
• Consumers should be able to substitute while(!tm.Terminated) with while(tm.NextInstruction()) after code has been refactored.

Answer 5

I'd make the following suggestions:

1. avoid placing limits (e.g., pre-declaring the tape size) if you can;
2. use properties and small functions to abstract away the lowest-level details;
3. use conditional expressions (cond ? y : n) in preference to if-then-else blocks;
4. traditionally, each instruction (state) in a Turing machine specifies, for each possible tape symbol, the symbol to write, the direction to move in, and the next instruction (state) to move to;
5. you want to make specifying and adding instructions much simpler;
6. it's okay to use short (even single-letter) enumeration symbols when the intent is obvious -- clarity and brevity often do go hand in hand.

Here's my first cut at implementing the above suggestions -- no doubt there are many places where people will disagree with my style!

// Rudimentary two-symbol Turing machine implementation.

public enum Sym { Y, N }
public enum Dir { L, R }
public const int Halt = -1;
public class TuringMachine
{
    internal struct SemiInstr { internal Sym Put; internal Dir Move; internal int GoTo; }
    internal struct Instr { internal SemiInstr OnY; internal SemiInstr OnN; }
    internal List<Instr> Prog = new List<Instr> { };
    internal Dictionary<int, Sym> Tape = new Dictionary<int, UserQuery.Sym> { };
    internal int Idx = 0;
    internal int IP = 0;
    internal int This => Prog.Count;
    internal int Next => This + 1;
    internal Sym SymAt(int idx) => (Tape.ContainsKey(idx) ? Tape[idx] : Sym.N);
    public int AddInstr(Sym onYPut, Dir onYMove, int onYGoTo, Sym onNPut, Dir onNMove, int onNGoTo)
    {
        var thisIP = This;
        Prog.Add(new Instr
        {
            OnY = new SemiInstr { Put = onYPut, Move = onYMove, GoTo = onYGoTo },
            OnN = new SemiInstr { Put = onNPut, Move = onNMove, GoTo = onNGoTo }
        });
        return thisIP;
    }
    public void SetTape(string syms, int startFrom = 0)
    {
        Tape.Clear();
        for (var i = 0; i < syms.Length; i++)
        {
            Tape[i + startFrom] = (Char.ToUpper(syms[i]) == 'Y' ? Sym.Y : Sym.N);
        }
    }
    public bool Step()
    {
        if (IP == Halt) return false;
        var instr = Prog[IP];
        var sym = SymAt(Idx);
        var semiInstr = (sym == Sym.Y ? instr.OnY : instr.OnN);
        var newSym = semiInstr.Put;
        var delta = (semiInstr.Move == Dir.R ? 1 : -1);
        var nextIP = semiInstr.GoTo;
        Tape[Idx] = newSym;
        Idx += delta;
        IP = nextIP;
        return true;
    }
    public void ShowTape()
    {
        var from = Math.Min(Idx, Tape.Keys.Min());
        var to = Math.Max(Idx, Tape.Keys.Max());
        Console.Write($"[{IP}] ");
        for (var i = from; i <= to; i++)
        {
            var sym = SymAt(i).ToString();
            Console.Write(i != Idx ? sym : "<" + sym + ">");
        }
        Console.WriteLine();
    }
    public void Run(int maxSteps = int.MaxValue)
    {
        IP = 0;
        Idx = 0;
        var stillRunning = true;
        while (stillRunning && 0 < maxSteps--)
        {
            ShowTape();
            stillRunning = Step();
        }
    }
}

Here's an example program:

    var tm = new TuringMachine();
    tm.AddInstr(Sym.Y, Dir.L, tm.This, Sym.Y, Dir.R, tm.Next); // Extend left.
    tm.AddInstr(Sym.Y, Dir.R, tm.This, Sym.Y, Dir.L, 0); // Extend right.
    tm.SetTape("NNNNNNNNNN", -5);
    tm.Run(20);