Markov algorithms: A universal model of computation

A.A. Markov (1903-1979) introduced his ‘Theory of algorithms’ in the year 1951. Markov algorithms can be interpreted as the computer architecture for memory with sequential access only: The computation is modeled as a deterministic transformation of an input string to an output string, example: ‘1+2’ => ‘3’, according to rewrite rules which are scanned sequentially. The main comprehensive treatment in English is:

A.A. Markov, N.M. Nagorny: The Theory of Algorithms, (English translate), Kluwer Academic Publishers in the year 1988.

Alphabet A = {0, 1, ..}, our illustrations use A = {0, 1}. Marker alphabet M = {α, β, ..}.

Sequence (ordered) P = P1, P2, .. of rewriting the rules (or productions), which are of 2 kinds:

Pi = x -> y (continue) or Pi = x ¬ y (terminate), where x, y ∈ (A ∪ M)*.

The rule P = x -> y applies to the present data string D when x takes place as a contiguous substring in D, where after this occurrence of x is substituted by y. The terminal rule stops the procedure.

Markov algorithm evaluates a partial function f: A* -> A* by transforming a data string D, step-by-step.

Initially, D is the input string s ∈ A*, and when the algorithm terminates, D = f(s). Between initial and final value, D is transformed by applying rewrite rule Pi = x -> y or Pi = x ¬ y.

The transformation D <- Pi (D) is selected according to the given execution rule:

Use the first rule which applies to the data string D, apply it at leftmost pattern match.

Illustrations:

A) Modify all 0s to 1s. P1: 0 -> 1. No terminal rule is required; algorithm stops whenever no rule applies.

B) Produce 0s forever: P1: ε -> 0. “ε” is the null string, it always matches to left of any input string.

C) Append prefix ‘101’:  P1:  ε ¬ 101. Terminal rule stops the rewriting procedure.

D) Append the suffix ‘101’. Require marker, M = {α}. Careful whenever sequencing rewrite rules!

P1:   α 0 -> 0 α, P2:   α1 -> 1 α, P3:  α ¬ 101, P4:  ε -> α

Rule P4 is performed first and produces the marker α. P4 appears last in the production sequence P, where it is protected by P3 from ever being executed once more. The top priority rules P1 and P2 move α from the starting to the end of data string. Whenever α reaches its destination, the terminal rule P3 transforms it to the suffix 101 and stops the process.

Notation:

Generally we sequence the rules by writing them on separate lines implicitly. In illustration, above the order in which the two rules P1:  α 0 -> 0 α, P2:  α1 -> 1 α appear, that is, P1 P2 or P2 P1, is inappropriate. In order to emphasize that a subset of rules might be permuted randomly among themselves, we might write these on similar line:

a) α 0 -> 0 α,  α1 -> 1 α
α ¬ 101
ε ->  α

Furthermore, P1 and P2 have identical structure. With a big alphabet A = {0, 1, 2, ..} we require |A| rules of the kind α B -> B α, where variable B ranges over A. In order to abbreviate the text, we have to write the algorithm as:

b) α B -> B α
α ¬ 101
ε ->  α

This is termed as a production schema, a Meta notation that implies or produces the actual rule sequence (a). The schema rule α B -> B α implies that relative order of the individual rules produced is irrelevant.

Algorithm design:

How do you discover Markov algorithms for particular tasks? Is there a software engineering discipline for Markov algorithms which leads you to compose a complex algorithm from the standard building blocks by following the general rules? Yes, the diligent Markov programmer soon discovers persistent ideas.

Recurrent issues and troubles in Markov programming:

i) As the data string can merely be accessed sequentially, that is, you cannot assign an ‘address’ to certain data of interest, you should identify the places in the string ‘where things occur’ by placing the markers. Therefore, the data string is utilized as a content accessed memory. This initial placement of the markers is the initialization phase.

ii) After the preliminary placement of markers, each and every operation on the data string is generally preceded by scan from the starting of the string to a particular marker. Let us call the substring having only of symbols from alphabet A, with markers eliminated, the ‘restricted data string’. We state the repeated scans for markers, followed by operations on the restricted data string that is the ‘operating phase’.

iii) At Different times throughout execution, at the latest whenever the operations on data string (restricted to the alphabet A) are completed, now useless or injurious markers clutter the data string. ‘Cleaning up’, that is, eliminating not needed markers, is non-trivial: when you place α -> ε too early in the production sequence, marker α might be wiped out as soon as it is made!

iv) Most of the simple Markov algorithms can be designed as executing in three phases: initialization, operating phase and clean-up phase. More complicated algorithms, of course, might include repeated creation and elimination of markers, with different operating phases in between.

v) Once you have the plan for Markov algorithm, it is frequently simple to see what kind of productions is required.

Recognizing and confirming the accurate order of such productions, though, is generally difficult. The presence or absence of particular markers in data string helps to prove that some productions can’t apply at a specific moment; therefore, they might be ignored when reasoning regarding what happens during some time-intervals.

vi) The critical step is to invent invariants which are maintained at each and every iteration. This is by far most significant method for understanding how an algorithm works and proving it to be accurate!

vii) When you see a Markov algorithm devoid of explanation of its logic, it is much hard to ‘reverse engineer’ the designer’s ideas. Thus we will just look at algorithms which are supported by the arguments regarding how and why they work.

The given illustrations exemplify frequently useful methods.

Generate a palindrome, f(s) = s sreverse, A = {0, 1}. We postulate the given invariant for the operating phase. Let s = sL sR be a partition of the data string s to a prefix sL and a suffix sR. Example: s = a b c d e, sL = a b, sR = c d e. At all times, the present string s has the form s =   sL γ sLreverse α sR. In the illustration above: s = a b γ b a α c d e. The marker γ marks the center of palindrome built so far from the prefix sL; α marks the boundary among the palindrome already built and the suffix sR yet to be processed. If we now eliminate the first letter of sR and copy it twice, to the left and right of γ, then the invariant is re-established, with sR shrunk and sL expanded: a b c γ c b a α d e .

0 β  - > β  0,  1 β  - > β  1, 0 β  - > β  0,  1 β  - > β  1 (Carry β0 or β1 and moves left)
γ β0 - > 0 γ 0,  γ  β1 - > 1 γ 1 (Carry has reached the center, generates a bit and its mirror image)
α 0 -> β0 α , α 1 -> β1 α (Eliminate the left-most bit of sR and save its value in markers β0 or β1)
α -> ε , γ ¬ ε (at end, eliminate the markers; notice terminating production!)
ε -> γ  α (at starting, make the markers at far left)

Reversing the string is a key part of constructing a palindrome. We can siply modify Algorithm 5 to just reverse a string by modifying the invariant s = sL γ sLreverse α sR to s = γ sLreverse α sR, and the rules γ β0

- > 0 γ 0,  γ  β1 - > 1 γ 1  to  γ  β0 - > γ 0,  γ  β1 - >  γ 1 .

The given illustration describes a method which uses a single marker for various purposes at distinct times, and therefore, is a bit hard to fathom.

Reverse the input string s: f(s) = sreverse

P1 α α α  -> α α  (A double α which merges with a single α gets trimmed back)
P2 α α B -> B α α (Double α’s function as the pseudo marker to wipe out single α’s!)
P3 α α ¬ ε
P4 α B’ B” -> B” α B’  (This schema stands for four rules of the kind  α 1 0  ->  0 α 1
P5 ε -> α  (gets executed continually, however P2 and P3  stop P5 from making more than 2 consecutive α’s)

This algorithm is best comprehended as performing in two phases.

Phase 1: If productions P4 and P5 are active, mixes continual initial placements of marker α with operations which reverse the restricted data string. Invariant of Phase 1: There are no 2 consecutive α’s in data string, therefore productions P1, P2, P3 do not apply.

Subsequent to phase 1, there is a short interlude where production P5 makes 2 α’s at the head of string.

Phase 2: The cleanup phase eliminates all the markers by activating productions P1 and P2. Invariant of Phase 2: The data string always has a pair of consecutive α’s. Thanks to ‘pseudo marker’ αα, one of P1, P2, P3 always applies and P4 and P5 no longer get functioned. At very end, the terminating production P3 wipes out the very last markers.

Double the input string s: f(s) = ss

Introduce markers α, γ to delimit portions of the present string with various roles. Let s = sL sR be a part of s into a prefix sL and a suffix sR . In common, the current string has form sL α  sR  γ sR . By eliminating the rightmost bit of sL and copying it twice at the head of all string sR, we maintain this invariant with sL shrunk and sR expanded. Some phases of the current string: s, s α  γ , sL α  sR  γ sR ,  α  s  γ s ,  ss.

β0  γ  - >  γ 0 ,  β1  γ  - >  γ 1  (carry β0 or β1 transforms back to 0 or 1).
β0 0 - > 0 β0,  β0 1 - >1 β0 , β1 0 - > 0 β1,  β1 1 - > 1 β1 (carry β0 or β1 moves to right)
α γ  0 ->  0 α γ ,    α γ 1 -> 1 α γ  (markers travel to the far right)
0 α -> α 0 β0 ,  1 α -> α 1 β1  (move one bit of sL to expand first sR and produce a carry β)
α -> ε , γ ¬ ε  (At end, eliminate the markers; notice terminating production!)
ε ->  α γ   (At beginning, make the markers at far left)

Serial binary adder:

Given 2 n-bit binary integers x = xn .. x1 x0 ,   y = yn .. y1 y0 , n≥ 0, evaluate their sum z = zn+1 zn .. z1 z0,

A = {0, 1, +, =}, M = {β0, β1}. β0, β1 store and transport the single bit.

Coding:  Input string: x + y = 0, Output string: = z.

Idea: The input string x + y = 0 gets converted to the intermediate strings of the form xL + yL = zR, where xL is xn .. xi+1 xi, yL is

yn .. yi+1 yi, zR is zizi-1 .. z1 z0 .

Since the bit pair xi, yi is being cut off from the tail of xL and yL, a sum bit zi is appended to front of zR.

Invariant I:  zR = xR + yR, where xR , yR are the tails cut off from x and y respectively. I hold initially.

The algorithm is built from the given components:

Full adder: The addition logic is symbolized by 8 productions which can be written in any order:

0β0=0  ->  =00 0β1=0  ->  =01 1β0=0  ->  =01 1β1=0  ->  =10
0β0=1  ->  =01 0β1=1  ->  =10 1β0=1  ->  =10 1β1=1  ->  =11

Save the least significant bit of xL:  0+ -> +β0   1+ -> +β1

Transport this bit β subsequent to the least significant bit of yL:

β00 -> 0β0 β01 -> 1β0 β10 -> 0β1 β11 -> 1β1

Such building blocks are sequenced in such a way that, at any time during execution, the string consists of at most one β:

•    Full adder
•    Transport β
•    Save the least significant bit of xL 
•    Remove “+”:    += -> =

Markov algorithms are one of some universal models of computation: you can program an algorithm to calculate anything ‘computable’. Example: there is a Markov algorithm which simulates a universal Turing machine.

We have observed simple copy and data movement operations usable for string matching and copying. In order to make such assertion of universality plausible, we now program simple control structures.

Latest technology based Theory of Computation Online Tutoring Assistance

Tutors, at the www.tutorsglobe.com, take pledge to provide full satisfaction and assurance in Theory of Computation help via online tutoring. Students are getting 100% satisfaction by online tutors across the globe. Here you can get homework help for Theory of Computation, project ideas and tutorials. We provide email based Theory of Computation help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Theory of Computation. Through Online Tutoring, you would be able to complete your homework or assignments at your home. Tutors at the TutorsGlobe are committed to provide the best quality online tutoring assistance for Theory of Computation Homework help and assignment help services. They use their experience, as they have solved thousands of the Theory of Computation assignments, which may help you to solve your complex issues of Theory of Computation. TutorsGlobe assure for the best quality compliance to your homework. Compromise with quality is not in our dictionary. If we feel that we are not able to provide the homework help as per the deadline or given instruction by the student, we refund the money of the student without any delay.