5. Consider the following signature of a language meant for describing a fixed computation by a...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
5. Consider the following signature of a language meant for describing a fixed computation by a fixed Turing machine M (the presumed do- main of discourse is natural numbers, which shall be used to number the steps of the computation and the cells of M's tape; it shall be assumed that the tape of M extends infinitely to the right, but has the leftmost cell, numbered 0; we shall need a special symbol, the end- of-tape marker, which shall always be written in the leftmost cell, so that M knows not to move left of the leftmost cell; the states of M are assumed to be 90, 91, etc., with go being the starting state, q₁ the ac- cepting state, and 92 the rejecting state; the symbols of M's alphabet are assumed to be so, 81, etc., with so being the blank and s1 being the end-of-tape marker): the constant symbol 0; • the unary function symbol s (successor' on natural numbers); • the binary predicate letter x < y ('number z is strictly less than number y'); • the binary predicate letter C(x,y) ('at step 2, the machine M scans cell tape number y'); • the unary predicate letter Q(x) ('at step , the machine M is in state qk'); • the binary predicate letter Sk(x, y) (at step x, the cell y contains symbol ak'). (a) Write a formula describing the initial configuration of M on the empty word given as input. (b) Write a formula saying that, at every step of the computa- tion, M scans exactly one cell of its tape. (c) Write a formula saying that, at every step of the computa- tion, M is in a unique state. (d) Write a formula saying that, at every step of the computa- tion, each cell of the tape contains exactly one symbol. (e) Suppose that the program of M contains the command qisk → 9;s R. Write a formula describing the effect the execution of this command has on the computation. (f) Do the same for the command qisk →qjsjL. (g) Write a formula asserting that M halts. HINT: Assume all the quantifiers in your formulas to range over natural numbers. 5. Consider the following signature of a language meant for describing a fixed computation by a fixed Turing machine M (the presumed do- main of discourse is natural numbers, which shall be used to number the steps of the computation and the cells of M's tape; it shall be assumed that the tape of M extends infinitely to the right, but has the leftmost cell, numbered 0; we shall need a special symbol, the end- of-tape marker, which shall always be written in the leftmost cell, so that M knows not to move left of the leftmost cell; the states of M are assumed to be 90, 91, etc., with go being the starting state, q₁ the ac- cepting state, and 92 the rejecting state; the symbols of M's alphabet are assumed to be so, 81, etc., with so being the blank and s1 being the end-of-tape marker): the constant symbol 0; • the unary function symbol s (successor' on natural numbers); • the binary predicate letter x < y ('number z is strictly less than number y'); • the binary predicate letter C(x,y) ('at step 2, the machine M scans cell tape number y'); • the unary predicate letter Q(x) ('at step , the machine M is in state qk'); • the binary predicate letter Sk(x, y) (at step x, the cell y contains symbol ak'). (a) Write a formula describing the initial configuration of M on the empty word given as input. (b) Write a formula saying that, at every step of the computa- tion, M scans exactly one cell of its tape. (c) Write a formula saying that, at every step of the computa- tion, M is in a unique state. (d) Write a formula saying that, at every step of the computa- tion, each cell of the tape contains exactly one symbol. (e) Suppose that the program of M contains the command qisk → 9;s R. Write a formula describing the effect the execution of this command has on the computation. (f) Do the same for the command qisk →qjsjL. (g) Write a formula asserting that M halts. HINT: Assume all the quantifiers in your formulas to range over natural numbers.
Expert Answer:
Answer rating: 100% (QA)
a The initial configuration of M on the empty word given as input can be described using the following formula C 00 Q 00 x Qk x for k 0 x Sk x y for all k y This formula asserts that at step 0 M is in ... View the full answer
Related Book For
Income Tax Fundamentals 2013
ISBN: 9781285586618
31st Edition
Authors: Gerald E. Whittenburg, Martha Altus Buller, Steven L Gill
Posted Date:
Students also viewed these programming questions
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
Managing Scope Changes Case Study Scope changes on a project can occur regardless of how well the project is planned or executed. Scope changes can be the result of something that was omitted during...
-
Vern Westby inherited a ticket from Anna Sjoblom, a survivor of the sinking of the Titanic, which had been pinned to the inside of her coat. He also inherited an album of postcards, some of which...
-
Will a belief in cultural relativism create inevitable ethics problems for international business executives?
-
Explain why the function is differentiable at the given point. Then find the linearization L(x, y) of the function at that point. f (x, y) = 1 + x ln(xy - 5), (2, 3)
-
Meghann Patrick is a former employee of Altria Group Distribution Company. After her employment was terminated, Patrick sued Altria and a supervisor at Altria, alleging employment-related claims...
-
Effect of order quantity on special order decision Ellis Quilting Company makes blankets that it markets through a variety of department stores. It makes the blankets in batches of 1,000 units. Ellis...
-
How can a healthcare business increase its productivity and profitability using the disciplines found in Six Sigma?
-
The proposed rates were not in the range the CEO expected given the pricing analysis. The CEO has asked the pricing actuary to verify the total projected loss cost excluding potential large storm...
-
An eight-year, $26892 noninterest-bearing promissory note is discounted 6% compounded quarterly and sold to a finance company three years and nine months after issue. What are the proceeds of the...
-
a Java program that calculates how much a person earns in a month if the salary is one penny the first day, two pennies the second day, four pennies the third day, and continue to double each day the...
-
Identify an example of a management scenario from current events involving adverse selection or moral hazard. Discuss some methods with your classmates for correcting the potential problems of the...
-
During the Baroque era, Western instruments began to emerge in their modern forms. For the first time in history, composers began to develop ensembles and genres of music solely devoted to...
-
2. A taxpayer that is a commercial company carries out hybrid acts or activities (taxed and exempt) for the purposes of the Value Added Tax; Last month, he acquired office furniture in cash that he...
-
A project manager and key team members were preparing a RACI chart for the major project work packages and activities. In each row they only assigned one "A" (for Accountable) to a single resource....
-
On March 1, Job 10 had a beginning balance of $500. During March, direct materials of $800 and direct labor of $300 were added to the job. Overhead is applied to production at a rate of 40% of direct...
-
One of the significant and relevant accounts for this cycle is equipment. For this account, what would typically be the most relevant assertions for the auditor to consider? Why is it important for...
-
Skyler is covered by his company's health insurance plan. The health insurance costs his company $3,500 a year. During the year, Skyler is diagnosed with a serious illness and the health insurance...
-
If Charles, a 16-year-old child model, earns $50,000 a year and is completely self supporting even though he lives with his parents, can his parents claim him as a dependent? Why or why not?...
-
Olive Corporation was formed and began operations on January 1, 2012. The corporation's income statement for the year and the balance sheet at year-end are presented below. The corporation made...
-
What is an off-by-one error?
-
Will the universality of management continue to be true in the future? Why or why not?
-
Describe what a manager does. How does the work of managers differ from that of nonmanagerial employees?
Study smarter with the SolutionInn App