1. Computability (a) Prove that the Empty Language problem is undecidable by reducing the Any Inputs...

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."

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