A question about decidable and undecidable problems

Question

Maybe this question is not very smart but I really wanna learn this thing. also, I need someone who is familiar with printing 42 problem and zero program problem.

This is the context:

Consider the problem of determining whether a number belongs to a set. This problem is easy for the following sets:

• The set of odd numbers
• The set of even numbers
• The set of prime numbers
• The set of numbers that can be written as a sum of five square numbers

For every one of these sets, a program can be written that accepts a whole number as input and—depending on whether the input is in that set—outputs a yes or no answer.

However, there are other types of sets. This chapter has shown that there are certain sets of whole numbers for which no computer program can be written that can decide if they are in the set or not. For example,

• The set of numbers of programs that will output 42 for some input
• The set of numbers of programs that always output a 0"

The Outer Limits of Reason: What Science, Mathematics, and Logic Cannot Tell Us by Noson S. Yanofsky

First of all, I should say that I am a self-learning in this area, so I don't have very good knowledge about this stuff. so, in this context, I don't get two parts. If anyone could help me, I would very appreciate it.

the first part is: "there are other types of sets. This chapter has shown that there are certain sets of whole numbers for which no computer program can be written that can decide if they are in the set or not." what are they. is the writer talking about inputs/ arbitrary whole numbers or certain sets of whole numbers?

second, I don't get this part at all and somewhat, this part is making me confused about the former question:

• The set of numbers of programs that will output 42 for some input
• The set of numbers of programs that always output a 0"

if you rewrite this part in another form, I think I would comprehend it because I think this is a grammatical confusion. thank you in advance

Answer 1

When the author talks about "number of programs", they mean numbers that represent programs. Normally, we think about programs of being strings of characters (e.g., Java programs) but we can also represent programs as numbers. The easiest way to see this is to think how they're represented inside your computer. That string of characters is just a big list of zeros and ones inside the computer, and a "big list of zeros and ones" is just a number written out in binary. Formally speaking, "programs" here are probably Turing machines but it won't hurt you to think of computer programs in whatever language you're familiar with.

The technique of using natural numbers to represent arbitrary objects like this is sometimes called "Gödel numbering", as it was first used by Kurt Gödel to prove things about logic. He encoded logical formulas as numbers, which allowed him to write formulas about formulas, in much the same way as a compiler is a computer program that operates on computer programs, and a universal Turing machine is a Turing machine that operates on Turing machines.

"... [T]here are certain sets of whole numbers for which no computer program can be written that can decide if they are in the set or not." What are "they"? Is the writer talking about inputs/arbitrary whole numbers or certain sets of whole numbers?

That's not a very well-written sentence. The interpretation that makes most sense to me (the only one I can think of that makes the statement true) is, "There are certain sets of whole numbers for which no computer program can be written that decides whether its input is in that set."