1
$\begingroup$

Our professor explained that all programs can be thought of as the set of natural numbers, while decision problems can be thought of as the set or rational numbers.

Our notes say a decision problem can be represented as a function which takes a natural number as input and maps it to either 0 or 1. That the range is 0 or 1 is obvious but why is the input a natural number? What does it represent? I understand that a program can be represented by a natural number but a program isn't the input for a decision problem, is it? What is the input of a decision problem and why is it represented by a natural number?

$\endgroup$

2 Answers 2

0
$\begingroup$

The number doesn't have to represent anything but itself. E.g. "Is a given natural number $n$ even" is a decision problem. Its input is $n$.

We aren't really only interested in decision problems on natural numbers. "Does program $p$ halt when started without arguments" is also a decision problem.

But to consider decision problems on some set $A$ it must be possible to encode all its elements by a finite string in some finite alphabet (otherwise we couldn't use them as input to anything). And for any finite alphabet, the set of all finite strings is countable and you can easily encode each string by a natural number and vice versa.

$\endgroup$
0
$\begingroup$

It's probably easier to understand if you think of a program as a bit-string, i.e., an element of $\{0,1\}^*$; and think of a decision problem as a function that maps a bit-string to either 0 or 1, i.e., a function $\{0,1\}^* \to \{0,1\}$. The input to the decision problem is a bit-string.

Why is this reasonable? Any program can be expressed as a sequence of bits (e.g., convert each character to bits, and concatenate them). The input to the program can be expressed as a sequence of bits. So everything is bits.

Hopefully that approach makes sense.

Now, why does your professor/textbook talk about natural numbers instead of bit-strings? That's just a convention. It turns out that every bit-string can be encoded as a natural number, and vice versa. Given a bit-string, you can think of it as the binary representation of a number; and given a number, you can turn it into a bit-string by expressing it in binary. So bit-strings and natural numbers are in some sense interchangeable or equivalent.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.