1. Computability (a) Prove that the Empty Language problem is undecidable by reducing the Any Inputs...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
1. Computability (a) Prove that the Empty Language problem is undecidable by reducing the Any Inputs problem to it. Make sure that all of the details of the reduction are clearly specified. You may use a diagram to assist with this if you wish. (c) Grumble, a grumpy wizard, claims to have done the following. • Identified a decision problem over graphs, which he calls the Balrog prob- lem, for which he has a (secret) Turing machine which will solve any instance of the Balrog problem in at most n³ +n²+5 steps for an input of size n. • Found a (deterministic) Turing machine which transforms an input w to the 3-SAT problem to an input B(w) to the Balrog problem in at most n² + 4 steps for an input of size n. ● Found a (deterministic) Turing machine which transforms an input w to the Hamiltonian circuit problem to an input H(w) to the 3-SAT in at most n¹ +7 steps for an input of size n. Grumble claims that this establishes that the Balrog problem is NP-complete. Do you agree or disagree? Explain your answer. (d) Gimli the Gumby, a friend of a more famous Gimli, has written the following discussion. There are a number of incorrect statements in the paragraph below. Identify all incorrect statements and justify each of your answers. Note: A single sentence counts as one statement. "Algorithms are an expression of knowledge that makes computers work. In order to solve a particular computational problem, such as finding the factors of a given number, or sorting a list of students by their student number, an algorithm must be developed and implemented. It comes as a great surprise to many people that there are some problems for which there is no algorithm possible. These are known as undecidable problems and include the Halt- ing problem for Turing machines, the Hamiltonian Circuit problem, the busy beaver problem, the tile problem and the blank tape problem. Alan Turing was the first to show there was an undecidable problem, and since that time many other problems have been shown also to be undecidable. This is done by reducing a problem (say A) with unknown status to a problem known to be intractable (say B). From this reduction it is simple to show that problem A must be intractable using the Pumping Lemma. The existence of unde- cidable problems means that certain properties of programs cannot be guar- anteed. The Church-Turing thesis, which states that anything computable can be performed by a Turing machine, indicates that we cannot avoid un- decidable problems by changing technologies. Undecidable problems are also an issue for nondeterministic pushdown automata and nondeterministic finite state automata, as nondeterminism introduces computations based on chance. Unrestricted grammars do not have any issues with undecidable problems, as there are by definition unrestricted. Note though that NP-complete and other intractable problems are all decidable." 1. Computability (a) Prove that the Empty Language problem is undecidable by reducing the Any Inputs problem to it. Make sure that all of the details of the reduction are clearly specified. You may use a diagram to assist with this if you wish. (c) Grumble, a grumpy wizard, claims to have done the following. • Identified a decision problem over graphs, which he calls the Balrog prob- lem, for which he has a (secret) Turing machine which will solve any instance of the Balrog problem in at most n³ +n²+5 steps for an input of size n. • Found a (deterministic) Turing machine which transforms an input w to the 3-SAT problem to an input B(w) to the Balrog problem in at most n² + 4 steps for an input of size n. ● Found a (deterministic) Turing machine which transforms an input w to the Hamiltonian circuit problem to an input H(w) to the 3-SAT in at most n¹ +7 steps for an input of size n. Grumble claims that this establishes that the Balrog problem is NP-complete. Do you agree or disagree? Explain your answer. (d) Gimli the Gumby, a friend of a more famous Gimli, has written the following discussion. There are a number of incorrect statements in the paragraph below. Identify all incorrect statements and justify each of your answers. Note: A single sentence counts as one statement. "Algorithms are an expression of knowledge that makes computers work. In order to solve a particular computational problem, such as finding the factors of a given number, or sorting a list of students by their student number, an algorithm must be developed and implemented. It comes as a great surprise to many people that there are some problems for which there is no algorithm possible. These are known as undecidable problems and include the Halt- ing problem for Turing machines, the Hamiltonian Circuit problem, the busy beaver problem, the tile problem and the blank tape problem. Alan Turing was the first to show there was an undecidable problem, and since that time many other problems have been shown also to be undecidable. This is done by reducing a problem (say A) with unknown status to a problem known to be intractable (say B). From this reduction it is simple to show that problem A must be intractable using the Pumping Lemma. The existence of unde- cidable problems means that certain properties of programs cannot be guar- anteed. The Church-Turing thesis, which states that anything computable can be performed by a Turing machine, indicates that we cannot avoid un- decidable problems by changing technologies. Undecidable problems are also an issue for nondeterministic pushdown automata and nondeterministic finite state automata, as nondeterminism introduces computations based on chance. Unrestricted grammars do not have any issues with undecidable problems, as there are by definition unrestricted. Note though that NP-complete and other intractable problems are all decidable."
Expert Answer:
Answer rating: 100% (QA)
1 Empty Language Problem and Any Inputs Problem The Empty Language problem asks whether a given lang... 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
-
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...
-
The Crazy Eddie fraud may appear smaller and gentler than the massive billion-dollar frauds exposed in recent times, such as Bernie Madoffs Ponzi scheme, frauds in the subprime mortgage market, the...
-
The P04_18.xlsx file contains a single-table Data Model on a companys sales and a single blank worksheet. The goal is to create a pivot table that shows the ratio of average revenue per transaction...
-
A. Opportunity costs is 1. The money a business loses in a bad investment 2. The value of the best foregone opportunity 3. The price an individual pays for making a mistake 4. Opportunity knocks but...
-
What is the revenue growth trend of the potential partner in the last three years? How do the potential partner's financial ratios compare to industry benchmarks? Are there any outstanding tax...
-
The independent auditor must evaluate a client's system of internal control to determine the extent to which various auditing procedures must be employed. A client who uses a computer should provide...
-
Kansas Seed Corn Supplies, a company with 100,000 shares of common stock outstanding, had the following transactions during 20X1, its first year in business: Sales ....... 1,000,000 pounds @ $5...
-
The Maderas y Maderas company manufactures its products in its only production department. In any period they begin to manufacture a batch of 500 restaurant-type tables, at the end of the period they...
-
1. Using the spreadsheet model from Case 2.1 as a starting point, use Solver to find the optimal set of projects to approve. The solution should maximize the total NPV from the approved projects, and...
-
Carrie repossessed a property with a fair market value of $19,000 on the date of repossession. Her basis in the property is $11,000, and the costs of repossession were $1,200. What is Carrie's gain...
-
From the following table, find your mechanism and calculate the mobility of it using Kutzbach criterion. M i (a) (b) m (e) A (i) (f) (j) (c) (g) (d) (h) 19 77777
-
Find the following indefinite integrals using u-substitution: a) f39ex e13x - 9dx Find the following indefinite integrals: b) 20 sech (5x) (4 + tanh(5x))4 dx Consider the region bounded by y = 3,...
-
2. Consider the problem of forecasting the return on a portfolio comprised of two assets. The daily return on the portfolio is
-
Suppose that we have an economy with many identical households. There is government that exogenously consumes some output and pays for it with lump sum taxes. Lifetime utility for a household is: U...
-
The graphs below show the production possibility frontiers (PPFS) of Carolinia and Brodenstan, two countries that produce only coffee and bread. Initially-before specialization and trade-Carolinia...
-
Solve the below question. Let a and b be in the set of Natural Numbers. More formally, a bN Select a few random values for a and b, and keep the numbers small. Try to answer the following questions,...
-
On April 29, 2015, Auk Corporation acquires 100% of the outstanding stock of Amazon Corporation (E & P of $750,000) for $1.2 million. Amazon has assets with a fair market value of $1.4 million (basis...
-
Ken paid the following amounts for interest during 2012: Qualified interest on home mortgage...........................................$4,700 Auto loan...
-
Dr. George E. Beeper is a single taxpayer. He lives at 45 Mountain View Dr., Apt. 321, Spokane, WA 99210. Dr. Beeper's Social Security number is 775-88-9531. Dr. Beeper works for the Pine Medical...
-
Phil and Linda are 25-year-old newlyweds and file a joint tax return. Linda is covered by a retirement plan at work, but Phil is not. a. Assuming Phil's wages were $27,000 and Linda's wages were...
-
(a) Express the magnitude of the electric field inside the strip in Figure 27.43 in terms of the width \(w\) of the strip and the potential difference \(V_{\mathrm{RL}}\). (b) Given the magnitude...
-
Draw the magnetic field lines associated with the magnets in Figures \(27.1 b-d\) (both outside and inside the magnets). Assume that the pole on the left of each magnet is the north pole. Figure 27.1...
-
A compass sits on a table with its needle pointing to Earth's North Pole. A bar magnet with its long axis oriented along an east-west line is brought toward the compass from the east. If the needle...
Study smarter with the SolutionInn App