Programs can solve (some) problems

Computational problems exist "in the ether", a theoretical mapping of inputs to outputs. But such a mapping is not useful if we can't actually determine what the right output is for any input. For example, we might know that there is an answer to the question "Is there a route between these two cities?", but knowing there's an answer is not as useful as knowing the answer itself!

Furthermore, not only would we want to be able to determine the answer for some input, but we want to do so automatically, with some sort of mechanical process. For this, we want a program.

💡 DEFINITION

A program is a mechanical process for producing some output from an input.

But we don't care about just any program. For any computational problem, we want a program that determines the outputs for that computational problem. In other words, we want a program that computes that problem:

💡 DEFINITION

A program \(P\) solves or computes a computational problem \(F\) if for each string \(I\), the output of running \(P\) on \(I\) agrees with the output \(F(I)\).

In this chapter, we will encounter our first type of program, the String-In String-Out Python Program, as defined by What can be computed?

SISO Python programs

Because this formalism comes from What can be computed?, the formal definition of a SISO Python program is not reproduced here. Instead, please look at section 2.5 of What can be computed?.

The following is only meant to complement the textbook by helping you practice the concept and get immediate feedback.

👀 EXAMPLE

Recall the problem MultiplyByTwo:

Problem MultiplyByTwo

a string representing an integer \(N\) in base-10

a string representing the integer \(2N\) in base-10. If the input is not a valid base-10 integer, return the string "no".

We saw earlier what the expected inputs and corresponding outputs should be. But is it possible to write a program that determines what the output is given an input? Absolutely! Try writing a SISO Python program below that solves MultiplyByTwo. Make sure your program meets the criteria for a SISO Python program:

  • It must have a main function at the top of the file.
  • The function must take in a single parameter.
  • The parameter must be treated as a string.
  • The return value of the function must be a string.

To make this exercise easier, your code will only be tested on inputs where the input string represents a valid base-10 number.

    Not all problems can be automated

    It turns out, solving a problem is not always possible. This gives rise to two important classes of computational problems:

    💡 DEFINITION

    A computational problem is:

    In other words, some problems can be solved by automated programs, and some can't.

    As discussed in the previous chapter, decision problems are especially important in theoretical computer science, so there are special terms that describe computable and uncomputable decision problems:

    💡 DEFINITION

    A decision problem is:

    Equivalently, the terms decidable and undecidable are the same as computable and uncomputable respectively, but restricted to decision problems only.

    For some problems, especially the ones we will encounter in this class, showing a problem is computable or decidable is straightforward: write a program to solve it! That will immediately show there is a program (in particular the one you wrote) to solve that problem. Technically, you still have to show your program agrees with the output of the problem for every possible input, but most of the time, a reasonable reader will be convinced by the source code of the program.

    In contrast, showing a problem is uncomputable or undecidable is trickier, and will be the focus of a later chapter. It's not sufficient to try to write a program to solve the problem and fail to do so. That might just mean you haven't figured out how to write that program, not that such a program is impossible to write.

    👀 EXAMPLE

    The problem MultiplyByTwo is computable because the program you wrote above computes the problem!

    Some problems can be partially automated

    Just because some problems can't be solved with a program doesn't mean all hope is lost. It turns out, for some computational problems, a program can be written to automatically determine the answer in some cases but not others. This motivates the classification of recognizable problems:

    💡 DEFINITION

    A computational problem is recognizable if there is a program that:

    1. Terminates with the correct output for all positive instances (inputs where the problem outputs anything other than "no").

    2. For any negative instance (an input where the problem outputs "no"), either terminates with the correct output or goes into an infinite loop.

    A program that meets the above criteria for a computational problem is said to recognize that problem.

    Looking at this definition, notice that for negative instances, the program may produce the right answer or it may go into an infinite loop. But, that means that if the program tries to solve a problem and terminates with the right answer for all negative instances, then that program still meets the definition for recognizing the problem. At the same time, that same program also solves the problem fully! That means every program that computes a problem also recognizes that problem. In other words, all computable problems are recognizable.

    If you're interested in exploring further, a few interesting points:

    Languages can be computable and recognizable

    Recall there is a deep relationship between languages and decision problems: for every language, there is a corresponding decision problem that asks "Is the input string in the language?" This means a language can be classified as computable, uncomputable and/or recognizable based on the classification of its corresponding decision problem.

    More directly, we can classify a language as follows:

    Of course, languages will be computable or uncomputable based on if they are decidable or undecidable.