Post machine simulates Turing machine:
Assume that the TM M encompass the alphabet A = {0, 1, <, > }, where the angular brackets are employed to delimit the finite part of the tape which initially includes the input and later gets expanded to delimit the part of the tape which has been visited so far. Assume that the M’s transition function be of form f: Q x A -> Q x A x {L, R}.
We sketch the design of Post machine P which simulates M utilizing the alphabet B = {0, 1, <, >, #}. The fundamental idea is straight-forward, the details are complicated and will be skipped.
Let consider a configuration where M is in the state q and presently reads the (bold) symbol x of the tape:
M: < B y x z C>, with y, x, z ∈ A and B, C ∈ A*. That is, we focus attention on what occurs to x and to its two neighbor symbols y to left and z to the right, and merely carry all along the remaining parts of the tape, B and C.
In this configuration, M performs either a move-right transition q, x -> q’ x’ R or move-left transition q, x -> q’ x’ L
Post machine P’s state space comprises a subspace that is in 1-to-1 correspondence with the state space Q of TM M. Devoid of danger of confusion; we call this subspace Q and select its states with similar label as the corresponding state of M. When referring to a state q, the context will make it apparent whether we signify the state qM of M or qP of P. P’s state space comprises additional states, to be introduced as required, as in general a single transition of M needs a sequence of transition s of P.M’s configuration: state q, tape < B y x z C > is modeled as P’s configuration: state q, tape x z C > < B y
The encoding is practically forced, as P should inspect the similar symbol x as M does, however the only symbol it can examine is at the head of queue. Since M executes a transition q, x -> q’ x’ R or q, x -> q’ x’ L, P should be programmed to convert its queue in a corresponding manner. First try, that doesn’t quite work.
The easy case, that is, a move-right transition q, x -> q’ x’ R:
M: q, < B y x z C > becomes q’, < B y x’ z C > P: q, x z C > < B y becomes q’, z C > < B y x’
The single P transition attains accurately the needed transformation.
The cumbersome case, a move-left transition q, x -> q’ x’ L:
M: q, < B y x z C > becomes q’, < B y x’ z C> P: q, x z C > < B y should become q’, y x’ z C > < B
P’s transformation needs a complete rotation of queue in order to get the tail symbol to the head of queue. The rotation is possible when there is a distinguished symbol # which tells us when to stop. Therefore, the tentative encoding employed so far fails for a move-left transition and should be corrected.
Accurate encoding of M’s configuration in P’s configuration: Place a marker # two slots to left of the scanned symbol x. ‘To the left’ is interpreted in a circular manner, as when head and tail were glued altogether, and therefore # appears as next-to-last symbol in the queue.
M’s configuration: state q, tape < B y x z C > is modeled as
P’s configuration: state q, tape x z C > < B # y
Simulating the move-right transition q, x -> q’ x’ R:
M: q, < B y x z C > becomes q’, < B y x’ z C > P: q, x z C > < B # y becomes q’, z C > < B y # x’
Unluckily, this former ‘easy case’ has become more complex, as the consecutive pair # y should be permuted to y #. This can be attained by using auxiliary states and complete rotation.
Simulating the move-left transition q, x -> q’ x’ L, focus on two neighboring symbols to the left of scanned symbol x:
M: q, < B y z x C > becomes q’, < B y z x’ C > P: q, x C > < B y # z becomes q’, z x’ C > < B # y
Again, the consecutive pair # y should be permuted to y #, attained by using auxiliary states and complete rotation.
Two more cases should be considered, if M’s read or write head is placed at either end of tape visited so far, on a symbol <or>, and probably extends the visited part. In sum up, the design of a PM which simulates a random TM is theoretically straightforward once one mastered the acrobatics of the P’s queue rotations.
Therefore, we have completed cycle TM ≥ MA ≥ PM ≥ TM which verifies the computational equivalence of such three universal models of the computation.
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.
Morphology of algae tutorial all along with the key concepts of Algal Morphology, Unicellular Forms, Colonial Algae, Filamentous Forms, Heterotrichous Forms, Thalloid Forms and Polysiphonoid Forms
www.tutorsglobe.com offers carboxylic acids homework help, carboxylic acids assignment help, online tutoring assistance, organic chemistry solutions by online qualified tutor's help.
concept of competitive markets along with key concepts of perfect competition, short-run market equilibrium, market equilibrium, long-run market equilibrium and incidence, Market Equilibrium, Cost and Freight Price , answering questions of managerial economics tutors, homework help, assignment help.
total no. of coils = 24/4= 6; coils per phase = 12/3= 4; no. of coils of groups per phase = 3 x 2 = 6
www.tutorsglobe.com offers mechanism of electrophilic a-substitution homework help, assignment help, online tutoring assistance, organic chemistry solutions by online qualified tutor's help.
www.tutorsglobe.com offers Concept of Equivalent Production homework help, assignment help, case study, writing homework help, online tutoring assistance by accounting tutors.
leave all your academic anxiety to family law assignment help and secure your dream grades with ease at low prices.
Force-Centre of Gravity and Equilibrium tutorial all along with the key concepts of Concept of Force, Types of Force, Concepts of Equilibrium, Types of Equilibrium, Resultant and Equilibrium Forces, Moment of a Force, Principles of Moments, Conditions of Equilibrium and Principle of Floatation
TutorsGlobe.com Elementary Units in Chemical Reactions Assignment Help-Homework Help by Online Access Chemistry Tutors
are assignments and coursework your biggest nightmare? avail aerospace engineering assignment help to secure maximum marks.
A plastic in a very broad sense is defined like any non-metallic material which can be moulded to shape.
Transformers tutorial all along with the key concepts of Energy Losses in a Transformer, Mutual Inductance, Self-Inductance, Inductance of Solenoid, Energy Stored by an Inductor and Transients in R-L Circuits
tutorsglobe.com programming in web-development assignment help-homework help by online computer programming tutors
bluetooth is a standard communications protocol mainly designed for low power consumption, along with a short range (see table below). since the devices make use of a radio (broadcast) communications system.
Seeking for top-notch Thermodynamics Assignment Help? We provide apt assistance to score high at low prices!
1947977
Questions Asked
3689
Tutors
1484994
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!