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...
-
Refer to the data in Problem 5-4A. Required 1. Journalize the adjusting and closing entries. 2. Determine the December 31, 2017, Capital balance for Marvin's Fine Gems. In Problem 5-4A The trial...
-
Iris tried not to smile. Of course, it isnt technically a disaster, she explained, but I understand what you mean. How much information is lost? Joel looked at her in dismay. Lost? All of it! We had...
-
The pressure at which a pure substance changes its phase is known as the (a) Saturated pressure (b) Gauge pressure (c) Absolute pressure (d) None of these.
-
Malcolnn Reynolds Company has a balance in its Accounts Receivable control account of $11,000 on January 1, 2012. The subsidiary ledger contains three accounts: Nathan Company, balance $4,000;...
-
Provide an explanation of the importance of workplace meetings and explanation regarding to the norms of meetings? What constitute the bad meeting, does it affect employees performance?
-
Castelo Branco Lda is a manufacturer of video-conferencing products. Regular units are manufactured to meet marketing projections, and specialised units are made after an order is received....
-
Prepare the Income Statement, Statement of Retained Earnings, and Classified Balance Sheet using the following accounts for Year Ended Dec 31, 2023. When you prepare the statements, check off each...
-
6. A 120 V source is connected to a 300 W resistor. Find the resistance 7. If electricity costs 5 cents per kWhr, how much will it cost to run the 300 Watt circuit in question # 46 for an entire 24...
-
According to a national Gallup Poll of U.S. smartphone users, 75% upgrade their cell phone every two years. Use this information to answer the following questions. Show all required work. Be sure to...
-
Solve the equation 10-2+x=4. The only solution is a
-
The following are some assumptions given by the manager: The price is equal to $32 and is expected to increase by 20% every year At price equal to $50 the demand was 150. With each 5 Dollar increase,...
-
This problem explores the relationship between the mass of two blocks and their acceleration. Block A, of mass 2.0 kg, rests on a horizontal tabletop. There is negligible friction between Block A and...
-
A certificate of deposit (CD) offered by a new bank will pay $10,000 in three years. Your current bank offers a 9% rate on three year CDs. What is the most you should be willing to pay for the new...
-
A firm offers two products for sale. The marginal cost of one product is new zero once the first unit has been produced. The marginal cost of the other product rises as output rises. What would be...
-
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 the glass ceiling?
-
1. Whole Foods is a natural and organic foods retailer started by John Mackey and Renee Lawson in 1978. The company is headquartered in Austin, Texas. Today it operates 456 stores in the United...
-
Joe Maddon has been the manager of the Chicago Cubs since 2015. In his first year, he exceeded the expectations of most analysts and fans by leading the team to an appearance in the National League...
Study smarter with the SolutionInn App