1. Consider the Turing machine T over the input alphabet = {0, 1} with the state...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
1. Consider the Turing machine T over the input alphabet = {0, 1} with the state diagram below (the tape alphabet is = {0, 1, }). Convention: any missing transitions in the state diagram have value (grej,, R) 90 0:0. R. 1:0 R 0:0, R 1:1,L qacc 0:0 R DDR 41 grej (a) (5 points) Find a string of length 2 that is accepted by this Turing machine and justify your answer by describing the computation of T on this string. Your description should mention the contents of the tape, the state of the machine, and the location of the read/write head at each step in the computation. Hint: In class slides we've drawn pictures to represent the configuration of the machine at each step in a computation. You may do so or you may choose to describe these configura- tions in words. (c) (20 points) T is not a decider (Bonus, not for credit: how would you prove this?). Change the machine by changing one arrow in the state diagram to create a new Turing machine that is a decider. In other words, fill in the blank below in the formal definition of the Turing machines Tnew Tnew({90, 91, qacc, qrej}, {0, 1}, {0, 1, }, new, 90, qacc, grej) = where Snew ((q, x)) == -(((-)) if q = x= ((q, x)) otherwise where d is the transition function for T. Include in your explanation all of the following: ⚫ The full definition of new and the state diagram of Tnew A description of L(Tnew), using the state diagram to explain which strings are accepted and which are not. ⚫ A description, using the state diagram, to explain why all computations of Tnew halt. 1. Consider the Turing machine T over the input alphabet = {0, 1} with the state diagram below (the tape alphabet is = {0, 1, }). Convention: any missing transitions in the state diagram have value (grej,, R) 90 0:0. R. 1:0 R 0:0, R 1:1,L qacc 0:0 R DDR 41 grej (a) (5 points) Find a string of length 2 that is accepted by this Turing machine and justify your answer by describing the computation of T on this string. Your description should mention the contents of the tape, the state of the machine, and the location of the read/write head at each step in the computation. Hint: In class slides we've drawn pictures to represent the configuration of the machine at each step in a computation. You may do so or you may choose to describe these configura- tions in words. (c) (20 points) T is not a decider (Bonus, not for credit: how would you prove this?). Change the machine by changing one arrow in the state diagram to create a new Turing machine that is a decider. In other words, fill in the blank below in the formal definition of the Turing machines Tnew Tnew({90, 91, qacc, qrej}, {0, 1}, {0, 1, }, new, 90, qacc, grej) = where Snew ((q, x)) == -(((-)) if q = x= ((q, x)) otherwise where d is the transition function for T. Include in your explanation all of the following: ⚫ The full definition of new and the state diagram of Tnew A description of L(Tnew), using the state diagram to explain which strings are accepted and which are not. ⚫ A description, using the state diagram, to explain why all computations of Tnew halt.
Expert Answer:
Answer rating: 100% (QA)
c Consider the string 01 when given as input to the Turing machine The initial configuration will be q001 ie the state is q0 and head points at the lo... 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
-
If the NPV of an investment project is negative, management should: a. seek investment partners because the investment will cost more than planned b. invest as this is rare opportunity c. reject the...
-
The following additional information is available for the Dr. Ivan and Irene Incisor family from Chapters 1-5. Ivan's grandfather died and left a portfolio of municipal bonds. In 2012, they pay Ivan...
-
In Problems 3944, make the indicated conversions. a. 1 mm b. 1 mm = c. 1 m d. 1 m = m mm cm km
-
The second virial coefficient B' can be obtained from measurements of the density p of a gas at a series of pressures. Show that the graph of p/ p against p should be a straight line with slope...
-
VMware ESXi has been made very small. Why? After all, servers at data centers usually have tens of gigabytes of RAM. What difference does a few tens of megabytes more or less make?
-
In spring 1989, Michael Jordan and the Chicago Bulls were in Indianapolis, Indiana, to play against the Indiana Pacers. At the same time, Karla Knafel was singing with a band at a hotel in...
-
Tom Zopf owns and manages a computer repair service, which had the following trial balance on December 31, 2014 (the end of its fiscal year). Summarized transactions for January 2015 were as follows....
-
Use L . C 3 Assembly Instruction set table to convert the following code to Binary ISA codes: AND NOT RO,RO,#0 RO,RO AND RI,RI,#0 ADD RI,RI,#1 NOT RI,RI NOT RI.RI ADD RO,RO,RI
-
Compute the missing amount (?) for each company. (Amounts are in millions.) At the end of the year, which company had the highest net income? highest percent of net income to revenues? Babble Co....
-
Coca Cola is comparing two different capital structures. Given that Plan 1 all equity plan would result in 25,000 shares of stock outstanding at a market price of $13.5 per share. Plan 2 has 16,000...
-
You are currently only invested in the Natasha Fund (aside from risk-free securities). It has an expected return of 15% with a volatility of 19%. Currently, the risk-free rate of interest is 3.2%....
-
A big pharmaceutical company, DRIg, has just announced a potential cure for cancer. The stock price increased from $1 to $137 in one day. A friend calls to tell you that he owns DRIg. You proudly...
-
Your firm is planning to invest in an automated packaging plant. Harburtin Industries is an all-equity firm that specializes in this business. Suppose Harburtins equity beta is 0.88, the risk-free...
-
Four men and four women are shipwrecked on a tropical island. How many ways can they (a)Form four malefemale couples, (b)Get married if we keep track of the order in which the weddings occur,...
-
In mid-2009, Rite Aid had CCC-rated, 11-year bonds outstanding with a yield to maturity of 17.3%. At the time, similar maturity Treasuries had a yield of 2%. Suppose the market risk premium is 4% and...
-
Company XYZ plans to improve its outpatient services and wants to know which services are important to patients: large waiting rooms for family members, small rooms adjacent to recovery rooms,...
-
Describe basic managerial approaches to implementing controls and how these are implemented.
-
In 2012, Michael has net short-term capital losses of $2,000, a net long-term capital loss of $45,000, and other ordinary taxable income of $45,000. a. Calculate the amount of Michael's deduction for...
-
During 2012, Tom sold Sears stock for $10,000. The stock was purchased 4 years ago for $13,000. Tom also sold Ford Motor Company bonds for $35,000. The bonds were purchased 2 months ago for $30,000....
-
Ulysses and Penelope are married and file separate returns for 2012. Penelope itemizes her deductions on her return. Ulysses' adjusted gross income was $17,400, his itemized deductions were $2,250,...
-
List all of the factors you can think of that people use when deciding where to shop for clothes.
-
List the most important three factors for you personally when deciding where to shop for clothes.
-
Intel has dominated the computer chip industry. Beginning with the iconic advertising campaign Intel Inside, the company has created a large market for powerful processors. This has allowed Intel to...
Study smarter with the SolutionInn App