Register
Give an example of languages A and B where A, B, and (A - B) are all infinite languages, and A-B is decidable, but both A and B are not decidable. Explain. You can use the fact (proved in class) that ATM
186k views
4 votes
Give an example of languages A and B where A, B, and (A - B) are all infinite languages, and A-B is decidable, but both A and B are not decidable. Explain. You can use the fact (proved in class) that ATM is an undecidable language, and make A and B be languages which are defined using ATM

Hint: Once you think about what the languages A and B are, then the facts above about A, B and A-B are pretty easy to see.

User Mike Allen
by
7.9k points

1 Answer

5 votes

Final answer:

Languages A and B can be defined using the language ATM. A is the language of Turing machines that accept a string in ATM, B is the language of Turing machines that do not accept any string in ATM. The language (A - B) is decidable, but both A and B are undecidable.

Step-by-step explanation:

Let's consider languages A and B:

  • A is the language of all Turing machines that accept a string in the language ATM (the language of all Turing machines that halt on an empty input). A is infinite because there are infinitely many Turing machines that accept strings in ATM.
  • B is the language of all Turing machines that do not accept any string in ATM. B is also infinite because there are infinitely many Turing machines that do not halt on an empty input.
  • The language (A - B) consists of all Turing machines that halt on an empty input but are not in language B. This language is decidable because we can construct a Turing machine M that simulates both a Turing machine accepting a string in ATM and a Turing machine not accepting any string in ATM. If M accepts, it means the input Turing machine belongs to (A - B), and if M rejects, it means the input Turing machine does not belong to (A - B).
  • A and B are not decidable because ATM (which is used in defining both A and B) is an undecidable language.
User Questioner
by
8.2k points
Ask a Question
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.2m questions

11.9m answers

Other Questions

A piston-cylinder device fitted with stops in the cylinder walls contains 2.1 kg of water initially at 150 kPa and 30 °C. Heat is transferred to the system until the final temperature reaches 250 °C. The
A water towers lowest point is 405 ft and the main line is 6 feet below the ground. The ground elevation is at 276 ft. The main line travels 2.9 miles. The pipe will travel through the following flanged
The bulk modulus of a fluid if it undergoes a 1% change in volume when subjected to a pressure change of 10,000 psi is (a) 0.01 psi (b) 0.001 psi (c) 0.00001 psi (d) 0.000001 psi (e) none of these
A car has an initial speed of 10 m/s. It then undergoes a constant acceleration of 0.05 m/s^2 over a distance of 5 km. Determine: a) The car final speed. b) The time needed to travel the 5 km.
In solid motors, HTPB and PBAN are two common types of plasticizers. a) True b) False
Link Copied!