Solved

explanation of hierarchical notation of turing machine

Posted on 2013-05-21
241 Views
I have difficulties to understand the hierarchical notation of turing machine which is shown in the attached photo. Note that this is not assignment , it is already question and solution in the book but i didn't understand the solution. Please tell me the solution step by step , i didn't understand it.(i must understand it because it can be asked in final exam.) Or if you find and understand similar questions , you can explain it too.
Similar examples and the topic exist in the below links:

Any help is much appreciated.
turing-example.png
0
Question by:codeBuilder

LVL 84

Expert Comment

ID: 39186290
What question, and what solution are you asking for an explanation of?
0

LVL 31

Expert Comment

ID: 39186501
Your question is unclear and I am not exactly sure what you mean by Hierarchical Notation. The mechanics and underlying principles of Tiring Machines are very simple. The notation is a classic example of a notation being more complex than the concept it is trying to represent.
0

Author Comment

ID: 39186795
I assigned a png file. There are 2 questions and their answers in this png. But i didn't understand the answer. I want to learn solution step by step..
0

Author Comment

ID: 39186802
What does
R -> U R^2U a L^2U a
mean in the first question in png ?
Could you explain it?
0

LVL 37

Accepted Solution

TommySzalapski earned 500 total points
ID: 39187440
U: write a blank
R^2U: shift right until you hit a blank twice (so skip the first blank and stop at the second one)
a: print the a
L^2U: shift left until you hit a blank twice
a: print the a
0

LVL 37

Expert Comment

ID: 39187872
In your lecture notes that you posted they define some shorthand. Technically "shift right until the read head is over x" is not a valid Turing machine command, but you can create a machine that would do that. They use R subscript x to indicate such a machine.
And of course R^2 subscript x means do it twice.
0

Author Closing Comment

ID: 39195651
clear explanation
0

Featured Post

Introduction On a scale of 1 to 10, how would you rate our Product? Many of us have answered that question time and time again. But only a few of us have had the pleasure of receiving a stack of the filled out surveys and being asked to do somethi…
This article seeks to propel the full implementation of geothermal power plants in Mexico as a renewable energy source.
It is a freely distributed piece of software for such tasks as photo retouching, image composition and image authoring. It works on many operating systems, in many languages.
Internet Business Fax to Email Made Easy - With eFax Corporate (http://www.enterprise.efax.com), you'll receive a dedicated online fax number, which is used the same way as a typical analog fax number. You'll receive secure faxes in your email, fr…