Turing machine

http://en.wikipedia.org/wiki/Turing_machine

http://www.gotdotnet.ru/blogs/sos/5309/

http://www.gotdotnet.ru/blogs/vanka/5744/

 

http://lib.custis.ru/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0:%D0%A0%D0%B0%D1%81%D0%BF%D0%BE%D0%B7%D0%BD%D0%B0%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B8,_%D1%81_%D0%BE%D0%B4%D0%B8%D0%BD%D0%B0%D0%BA%D0%BE%D0%B2%D1%8B%D0%BC_%D0%BA%D0%BE%D0%BB%D0%B8%D1%87%D0%B5%D1%81%D1%82%D0%B2%D0%BE%D0%BC_0_%D0%B8_1

 

http://lib.custis.ru/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0:%D0%A0%D0%B0%D1%81%D0%BF%D0%BE%D0%B7%D0%BD%D0%B0%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D1%87%D0%B5%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%B8

 

http://en.wikipedia.org/wiki/Turing_machine_examples

 

namespace TuringMachine

{

    /// <summary>

    /// Represents a direction of the Turings machine head

    /// </summary>

    public enum Direction

    {

        Left = -1,

        Right = 1,

        Hold = 0

    }

   

    /// <summary>

    /// Defines a specific command that you intend to execute against a data source

    /// </summary>

    public class Command

    {

        private char? _state = null;

        private char? _scannedData = null;

        private char? _putData = null;

        private Direction? _direction = null;

        private char? _nextState = null;       

 

        private Command(){}

 

        /// <summary>

        ///

        /// </summary>

        /// <param name="state">Current state</param>

        /// <param name="scannedData">Scanned symbol</param>

        /// <param name="putData">New symbol</param>

        /// <param name="direction">Direction of the Turings machine head</param>

        /// <param name="nextState">Next state</param>

        public Command(char state, char scannedData, char putData, Direction direction, char nextState)

        {

            _state= state;

            _scannedData = scannedData;

            _putData = putData;

            _direction = direction;

            _nextState = nextState;

        }

 

        public char? State

        {

            get { return _state; }

        }

 

        public char? ScannedData

        {

            get { return _scannedData; }

        }

 

        public char? NextState

        {

            get { return _nextState; }

        }

 

        public Direction? Direction

        {

            get { return _direction; }

        }

 

        public char? Data

        {

            get { return _putData; }

        }

    }

 

    class Program

    {

        private static int _headPosition = 0;

        private static char[] _tape = null;

        private static char? _machineState = null;

        private static List<Command> _commands = new List<Command>();

        private static Command _currentCommand = null;

       

        static void Main(string[] args)

        {

            //3-state busy beaver program

            _machineState = ‘A’;

            _tape = new char[] { };

 

            _commands.Add(new Command(‘A’, , ‘1’, Direction.Right, ‘B’));

            _commands.Add(new Command(‘A’, ‘1’, ‘1’, Direction.Left, ‘C’));

            _commands.Add(new Command(‘B’, , ‘1’, Direction.Left, ‘A’));

            _commands.Add(new Command(‘B’, ‘1’, ‘1’, Direction.Right, ‘B’));

            _commands.Add(new Command(‘C’, , ‘1’, Direction.Left, ‘B’));

            _commands.Add(new Command(‘C’, ‘1’, ‘1’, Direction.Hold, ‘_’));

 

            while (!(Run() == ‘_’)) ;

 

 

            Console.ReadKey();

        }

 

        /// <summary>

        /// The Turing machine reads a symbol from its tape and proccess a command

        /// </summary>

        /// <returns>Next state of the Turing Machine</returns>

        public static char? Run()

        {

 

            Trace.WriteLine(" -=====================================================- ");

            try

            {

                _currentCommand = _commands.Single(o => ((o.State == _machineState) && (o.ScannedData == _tape[_headPosition])));

            }

            catch(Exception ex)

            {

                //If there is no such command or there are more the one command it generates an exception 

                Trace.WriteLine("Ambigous command");

                return ‘_’;

            }

 

           

            Trace.WriteLine("Current machine state: " + _machineState);

            Trace.WriteLine("Data on the tape: " + _tape[_headPosition]);

           

            _tape[_headPosition] = (char)_currentCommand.Data;

            _machineState = _currentCommand.NextState;

            MoveHead(_currentCommand.Direction);           

 

            Trace.WriteLine("New data on the tape: " + _currentCommand.Data);

            Trace.WriteLine("New state: " + _currentCommand.NextState);

            Trace.WriteLine(" Direction: " + _currentCommand.Direction);

 

            return _machineState;

        }

 

        /// <summary>

        /// Moves the Turing machine head and if it is neccessary extends the tape

        /// </summary>

        /// <param name="direction">A direction of the Turings machine head</param>

        public static void MoveHead(Direction? direction)

        {

            _headPosition += (int)direction;

            if (_headPosition == _tape.Length || _headPosition == -1)

            {

                Array.Resize(ref _tape, _tape.Length + 1);

                if (_headPosition == -1)

                {

                    Array.ConstrainedCopy(_tape, 0, _tape, 1, _tape.Length – 1);

                    _tape[0] = ;

                    _headPosition = 0;

                }

            }

 

        }

    }

}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s