Assignment Help - homework help

  Concept of Equivalence of TMs, PMs and Markov Algorithms

Equivalence of TMs, PMs and Markov algorithms

Aims: Prove the equivalence of three instead various models of computation. This equivalence supports the Church-Turing thesis which any of such models captures the concept of efficient computation.

A) Overview of concepts and proofs.
B) Post machines or tag machines.
C) TM simulates the Markov algorithm.
D) Markov algorithm simulates the Post machine.
E) Post machine simulates the TM.

Overview of concepts and proofs:

Out of the three models of computation considered in this section: Turing machines (or TM), Post machines (or PM) or the queue machines (or QM), and Markov algorithms (or MA), TMs are the most versatile ones. TM programmer can lay out his data all along the tape in any convenient way, designing ‘labels’ of his choice to recognize the different parts. The finite state controller can be programmed to look for any desired data item by scanning the tape till the corresponding label is encountered. Therefore, a TM can be programmed to simulate the direct access to its store, albeit with a terrific slow-down as compared to the RAM.

Post machines, by disparity, suffer from an access limitation to their store, a FIFO queue. The symbol is read and removed from the head of queue; symbols are appended to the tail of queue. This turns out, though, that a FIFO queue (dissimilar a LIFO queue, that is, a stack) can simulate a tape which supports local left-or-right-moves of the read or write head. To view how this works, imagine the head and tail of the FIFO queue to be glued altogether, generating a circular tape. The operation ‘remove the symbol at the head and append it at tail’ corresponds to a circular left shift, if the head of queue is pictured as facing left. The circular right shift can be simulated by L-1 circular left shifts, where L is current length of the queue. Therefore, crafty programming can conquer the access limitation of the FIFO queue and simulate the TM tape.

The finite state controller of TMs and PMs acts similar to a goto-program-the program counter can jump from anywhere to anywhere. As gotos can be employed to implement any control structure, the primitive however powerful FSM control of TMs and PMs imposes no limitations. The control structure of the Markov algorithms, on other hand, is strictly sequential. Scanning the rewrite rules from first to last, and data string from left to right, the first rewrite rule which applies, is executed at first pattern match. There is no explicit method to state a goto of the type ‘now continue using rewrite rule number so-and-so’.

Nonetheless, the sequential nature of Markov algorithm control structures is capable to simulate the unlimited jumps of an FSM. Let consider a subset of rewrite rules which mentally we want to relate with a ‘state’. We design labels for all of the states, say q1, q2, .., making sure that such labels remain distinguishable from anything else which might appear on the data string. Any rewrite rule L -> R intended to convert the data string D in a desired way is written as qi L -> qj R. When D initially comprises the label q1, referring to the ‘starting state’ q1, then rules are functioned from their subsets exactly as outgoing transitions are performed from their states. We utilize this simulation of goto-structures whenever designing the Markov algorithms which mimic FSM control.

In vision of the comments above and our experience with TMs, it is no surprise that the TMs can simulate both the Markov algorithms and PMs. In the given proofs of equivalence we will directly utilize only the first of such two assertions. We represent it by TM ≥ MA, signifying ‘TMs are at least as powerful as the Markov algorithms’. We then carry on with two less apparent assertions:  MA ≥ PM ≥ TM. Once such assertions are proved we close the circle TM ≥ MA ≥ PM ≥ TM that verifies the equivalence of all the three models of computation.

The last introductory comment regarding the concept of ‘universal machine or algorithm’. In verifying any of the inequalities TM ≥ MA ≥ PM ≥ TM, we could plan to present a universal instance of its class of machines. In another words, in proving PM ≥ TM we could represent a universal PM which has on its data string explanations d(M) and d(T) of an random TM M and its tape T, and which continues to interpret such descriptions step by step. This outcome in complex machines which spend their time mostly in pattern matching and copying.

We will rather proceed in a simpler and more proficient way, akin to the way that compilation is more proficient than interpretation. In order to verify PM ≥ TM, or any of other inequalities, we suppose an arbitrary TM M is given, and we construct a PM P tailor-made to simulate the specific TM M. As we know that there exist universal TMs, U, and as Markov algorithms and PMs can simulate any TM, comprising a universal TM U, it follows that there are universal Markov algorithms and universal PMs.

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.
Home | Company Overview | Services | Discover Q&A | Sitemap | Contact Us | T & C | Refund Policy | Copyright Policy | Blog | Q&A | Directory

©TutorsGlobe All rights reserved 2022-2023.