Welcome to Algorithm Simulator project.

Currently the project contains two following algorithms:

• Turing machine algorithm;
• Markov algorithm.

In the following sections you will see a short information and examples for the algorithms.

You can also access more documentation by following link (in ukr).

Active website: https://turing-machine.sloppy.zone.

Turing machine (TM)

Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed.

Example

Write a Turing machine that calculates the sum of two numbers written in the unary number system. The type of source data for any algorithm must be strictly defined.

Therefore, it is impossible to write a TM that calculates the sum of two numbers until the number system is specified. The unary number system is the so-called unitary (or bar) system: what is the number - so many ones.

The initial configuration of the Turing machine will be q1 (111...1 + 1...1)‚ where the number of ones in the first addend is x, and the number of ones in the second addend is y. The final configuration is required to be q0 (1...1), where the number of ones equals x + y.

To do this, let's develop a plan for the operation of the TM:

1. Erase the first unit;
2. Move the head to the right until the + sign, which should be replaced by 1;
3. Move the head to the left until the λ (empty character) sign;
4. Shift the head one character to the right and stop.

The implementation of each item of this plan requires its own state, so after writing down commands that implement the item of the plan, the state of the Turing machine should be changed.

Here you have the code. If you put "11+111" to the input - you'll get "11111" after running this code.

q0 1 → q0 1 R
q0 + → q1 1 R
q1 1→q1 1 R
q1 λ →  q2 λ L
q2 1 → q* λ

Markov algorithm

In theoretical computer science, a Markov algorithm is a string rewriting system that uses grammar-like rules to operate on strings of symbols. Markov algorithms have been shown to be Turing-complete, which means that they are suitable as a general model of computation and can represent any mathematical expression from its simple notation.

A Markov Algorithm over an alphabet A is a finite ordered sequence of productions x → y, where x, y ∈ A*. Some productions may be “Halt” productions. e.g.

abc → b
ba → x (halt)

Execution proceeds as follows:

1. Let the input string be w;

2. The productions are scanned in sequence, looking for a production x → y where x is a substring of w;

3. The left-most x in w is replaced by y;

4. If the production is a halt production, we halt;

5. If no matching production is found, the process halts;

6. If a replacement was made, we repeat from step 2.

Example

The algoritm:

aba → b
ba → b
b → a

Execution:

aabaaa
abaa
ba
b
a