Q115: Facts about diagonalization language

Question #115: The language L_d, diagonalization language, is the set of strings formed as follows:

The column enumerates the strings and the row enumerates the Turing machine. The table entry 0 means that the corresponding string is not in the corresponding language of Turing machine. In other words, if a_ij = 0, it means that j^th string is not in the i^th language. Now, take the diagonal of this table and flip all of the elements. The language thus formed by taking all flipped diagonal elements is called as diagonalization language. Which of the following is true based on above information?

1. The diagonal language disagrees in some column with every row of the table.
2. There can’t be any Turing machine describing diagonal strings.
3. There are more languages than Turing machines.
4. All of the above.

 

Solution:

Option 1 is correct because for M_i will disagree at w_i. We know by this argument that there is at least one language (diagonalization language) for which there is no Turing machine. Hence, the correct answer is option 4.

Q24: Hello-world tester

Question #24: Consider the following hypothetical program:

The program “Hello-world tester” takes two inputs, a program P and the input I for P. The program H prints “yes” if P on input I prints “hello, world”, otherwise H prints “no”. What do you think of such a program?

Options:

1. The program H can exist which can test any other program for some particular output.
2. The program H is very difficult to design.
3. The program H can’t exist since we can come up with a contradiction by replacing “no” with “hello, world” and taking a single input which both acts as program and input.
4. Both options 1 and 2 are correct

 

Solution:

This is one version of very famous halting problem, which states that we can’t detect whether any program on any input will ever halt or not. And, it’s undecidable over Turing machines! Hence, the correct answer is option 3.