TuringMachine

Program.cs

public static class Program
{
    private static void Main(string[] args)
    {
        var machine1 = new UniversalMachine(new[] {'0', '1'},
            new[] {"Mov", "B", "Bi", "OK"},
            new[]
            {
                "Mov 0 = Mov 0 >",
                "Mov 1 = Mov 1 >",
                "Mov _ = B _ <",
                "B 0 = B 0 <",
                "B 1 = Bi 1 <",
                "B _ = OK _ >",
                "Bi 0 = Bi 1 <",
                "Bi 1 = Bi 0 <",
                "Bi _ = OK _ >"
            }, @"01100100".ToCharArray());

        while (machine1.NextStep())
            Console.WriteLine(machine1.ToString());
        Console.WriteLine(Environment.NewLine + machine1.Steps);

        Console.ReadLine();

        var machine2 = new UniversalMachine(new[] { '.', '/', 'k' },
            new[] { "Init", "Mdot", "MDash", "Ret", "OK" },
            new[]
            {
                "Init _ = Init _ >",
                "Init . = Mdot _ >",
                "Init / = MDash _ >",
                "Init k = OK k >",
                "Mdot . = Mdot . >",
                "Mdot / = Mdot / >",
                "Mdot k = Mdot k >",
                "Mdot _ = Ret . <",
                "MDash . = MDash . >",
                "MDash / = MDash / >",
                "MDash k = MDash k >",
                "MDash _ = Ret / <",
                "Ret . = Ret . <",
                "Ret / = Ret / <",
                "Ret k = Ret k <",
                "Ret _ = Init _ >"
            }, @"/././../.../..../k".ToCharArray());

        while (machine2.NextStep())
            Console.WriteLine(machine2.ToString());
        Console.WriteLine(Environment.NewLine + machine2.Steps);

        Console.ReadLine();

        var machine3 = new UniversalMachine(new[] { '0', '1', 'x', 'y', '#' },
            new[] { "Search", "C0", "C1", "Ret", "OK" },
            new[]
            {
                "Search 0 = C0 x >",
                "Search 1 = C1 y >",
                "Search # = OK # >",
                "C0 0 = C0 0 >",
                "C0 1 = C0 1 >",
                "C0 # = C0 # >",
                "C0 _ = Ret 0 <",
                "C1 0 = C1 0 >",
                "C1 1 = C1 1 >",
                "C1 # = C1 # >",
                "C1 _ = Ret 1 <",
                "Ret 0 = Ret 0 <",
                "Ret 1 = Ret 1 <",
                "Ret # = Ret # <",
                "Ret x = Search 0 >",
                "Ret y = Search 1 >"
            }, @"0110100#".ToCharArray());

        while (machine3.NextStep())
            Console.WriteLine(machine3.ToString());
        Console.WriteLine(Environment.NewLine + machine3.Steps);

        Console.ReadLine();
    }
}

Tape.cs

public class Tape : LinkedList<Tuple<int, char>>
{
    public char this[int pos]
    {
        get { return this.FirstOrDefault(t => t.Item1 == pos)?.Item2 ?? '_'; }
        set
        {
            var node = Find(this.FirstOrDefault(t => t.Item1 == pos));
            if (node == null)
                if (Last.Value.Item1 < pos)
                    for (int i = Last.Value.Item1; i < pos; i++)
                        node = AddLast('_');
                else if (First.Value.Item1 > pos)
                    for (int i = First.Value.Item1; i > pos; i--)
                        node = AddFirst('_');
            if (node.Value.Item2 != value)
                node.Value = Tuple.Create(node.Value.Item1, value);
        }
    }

    public Tape()
    { }

    public Tape(IEnumerable<Tuple<int, char>> items) : base(items)
    { }

    public Tape(IEnumerable<char> items, int firstIndex = 0) : base(Convert(items, firstIndex))
    { }

    private static IEnumerable<Tuple<int, char>> Convert(IEnumerable<char> items, int firstIndex) =>
        from item in items
        select Tuple.Create(firstIndex++, item);

    public LinkedListNode<Tuple<int, char>> AddLast(char item)
        => AddLast(Tuple.Create((Last?.Value.Item1 + 1 ?? 0), item));

    public LinkedListNode<Tuple<int, char>> AddFirst(char item)
        => AddFirst(Tuple.Create((First?.Value.Item1 - 1 ?? 0), item));

    public override string ToString()
        => new string(this.Select(n=>n.Item2).ToArray());
}

UniversalMachine.cs

public class UniversalMachine
{
    public enum Direction
    {
        Left,
        Right
    }

    public Set<char> Alphabet { get; } = new Set<char>() {'_'};

    public Set<string> States { get; } = new Set<string>();
    public Tape Tape { get; } = new Tape();

    public string CurrentState { get; private set; }
    public string AcceptingState { get; }
    public bool IsRunning => CurrentState != AcceptingState;
    public int Position { get; private set; } = 0;
    public Direction CurrentDirection { get; private set; } = Direction.Right;

    public int Steps { get; private set; } = 0;

    public Tuple<string, char, Direction> CurrentFunction => Functions[CurrentState, Tape[Position]];

    public MultiDictionary<string, char, Tuple<string, char, Direction>> Functions { get; } =
        new MultiDictionary<string, char, Tuple<string, char, Direction>>();

    public UniversalMachine(IEnumerable<char> alphabet, IEnumerable<string> states, IEnumerable<string> functions, params char[] tape)
    {
        foreach (var symbol in alphabet)
        {
            if(symbol=='_')
                throw new Exception("'_' is implicitly implemented");
            if(!Alphabet.Add(symbol))
                throw new Exception(string.Format(@"{0} is already in the alphabet", symbol));
        }

        states = states.ReadOnce();
        if (states.Take(2).Count() < 2)
            throw new Exception(@"There must have more than 2 different states");
        foreach (var state in states)
        {
            if(state.Contains(' '))
                throw new Exception(string.Format(@"{0} can't contain space", state));

            if (!States.Add(state))
                throw new Exception(string.Format(@"{0} state is already defined", state));
        }
        CurrentState = States.First();
        AcceptingState = States.Last();

        var func = (
            from f in functions
            let split = f.Split(new[] {"=", " = ", " =", "= "}, StringSplitOptions.RemoveEmptyEntries)
            let cur = split[0].Split(' ')
            let next = split[1].Split(' ')
            select new
            {
                CurState = cur[0],
                CurSymbol = cur[1][0],
                NextState = next[0],
                NextSymbol = next[1][0],
                NextDir = next[2][0]
            })
            .ToArray();

        foreach (var f in func)
        {
            if (!States.Contains(f.CurState))
                throw new Exception(string.Format(@"State {0} is not defined", f.CurState));
            if (!States.Contains(f.NextState))
                throw new Exception(string.Format(@"State {0} is not defined", f.NextState));
            if (!Alphabet.Contains(f.CurSymbol))
                throw new Exception(string.Format(@"Symbol {0} is not defined", f.CurSymbol));
            if (!Alphabet.Contains(f.NextSymbol))
                throw new Exception(string.Format(@"Symbol {0} is not defined", f.NextSymbol));
            if (!new [] {'<', '>'}.Contains(f.NextDir))
                throw new Exception(@"Direction must be '<' or '>'");
        }

        var x = new MultiDictionary<string, char, Tuple<string, char, Direction>>(func.GroupBy(f => f.CurState)
            .ToDictionary(g => g.Key, g => g
                .ToDictionary(f => f.CurSymbol, f => Tuple.Create(f.NextState, f.NextSymbol,
                    (f.NextDir == '<') ? Direction.Left : Direction.Right))));

        foreach (var state in States)
        {
            var dico = new Dictionary<char, Tuple<string, char, Direction>>();

            foreach (var symbol in Alphabet)
                if (x.ContainsKey(state) && x[state].ContainsKey(symbol))
                    dico.Add(symbol, x[state][symbol]);
                else
                    dico.Add(symbol, null);

            Functions.Add(state, dico);
        }

        foreach (var symbol in tape)
        {
            if(!Alphabet.Contains(symbol))
                throw new Exception(string.Format(@"{0} is not in the alphabet", symbol));
            Tape.AddLast(symbol);
        }
    }

    public bool NextStep()
    {
        var func = CurrentFunction;
        Tape[Position] = func.Item2;
        CurrentState = func.Item1;
        CurrentDirection = func.Item3;

        switch (CurrentDirection)
        {
            case Direction.Left:
                Position--;
                Tape[Position] = Tape[Position];
                break;
            case Direction.Right:
                Position++;
                Tape[Position] = Tape[Position];
                break;
            default:
                throw new ArgumentOutOfRangeException();
        }

        Steps++;

        return IsRunning;
    }

    public override string ToString()
    {
        var list = new List<Tuple<char, char>>();

        foreach (var symbol in Tape)
        {
            char second;
            if (symbol.Item1 == Position && symbol.Item1 == 0)
                second = 'Î';
            else if (symbol.Item1 == Position)
                second = '^';
            else if (symbol.Item1 == 0)
                second = '|';
            else
                second = ' ';

            list.Add(Tuple.Create(symbol.Item2, second));
        }

        return new string(list.Select(i => i.Item1).ToArray()) +
               Environment.NewLine +
               new string(list.Select(i => i.Item2).ToArray());
    }
}