# 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:

**Computable**if there exists a program that solves that problem.**Uncomputable**if there is*no*program that solves that problem.

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:

**Decidable**if there exists a program that solves that problem.**Undecidable**if there is*no*program that solves that problem.

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:

Terminates with the correct output for all positive instances (inputs where the problem outputs anything other than

`"no"`

).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:

There is such a thing as a

*co-recognizable*problem, where a program can terminate with the right output for all negative instances and may or may not terminate for positive instances.In theoretical computer science literature, computable problems are called

**recursive**and recognizable problems are called**recursively enumerable**. Intuitively, programs to recognize a problem can*enumerate*through possible ways to get a positive answer until it finds such an answer. If there is no such positive answer, the program will keep searching forever.Another name for a recognizable problem is

**partially decidable**.Some problems are

**unrecognizable**, in that a program can't even terminate for positive instances!

## 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:

A language is decidable if a program can determine, for all inputs, if the input is in the language or not.

A language is undecidable if no program can determine, for all inputs, if the input is in the language or not.

A language is recognizable if a program can terminate with

`"yes"`

when the input is in the language, and either terminates with`"no"`

or goes into an infinite loop if the input is not in the language.

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