Question

Show that the problem of determining whether a program with a given input ever prints the digit is unsolvable.

Short answer

The given problem is unsolvable.

Step-by-step solution

Step 1:

Gale-Shapley algorithm (also known as deferred acceptance algorithm): This algorithm is used for finding a solution to the stable matching problem.

The members of one gender are the suitors while the members of the other gender are the suitees. This algorithm involves a sequence of rounds. Every suitor who was rejected in the previous round proposes to their highest ranking suitor who has not rejected their proposal in the previous rounds. A suitee rejects every proposal excluding the proposal of the one who ranks highest among all the suitors proposing to them. Then, unless they find a suitor more appealing than the highest ranking suitor, the proposal remains pending until each suitee has one pending proposal left. All the proposals that were pending are now accepted.

We have,

The given input ever prints the digit 1 .

Step 2:

Using the deferred acceptance algorithm,

Let A be the program that generates.

A generates when there is a long string of zeroes.

The possibility of it printing 1 is unknown.

Let A' be another program that generates.

A' will stop if and only if 1 is printed by program A .

We do not know if the program A' will end.

Hence this problem is unsolvable.