I am reading and trying to understand https://jeremykun.com/2012/02/23/p-vs-np-a-primer-and-a-proof-written-in-racket/ and https://jeremykun.com/2011/07/04/turing-machines-a-primer/, and the author author often talks about languages and problems interchangeably.


Definition: If a Turing machine halts on a given input, either accepting or rejecting, then it decides the input. We call an acceptance problem decidable if there exists some Turing machine that halts on every input for that problem. If no such Turing machine exists, we call the problem undecidable over the class of Turing machines.

I think I understand the definition of decidability for languages:

Language $L$ is decidable iff there is a Turing Machine that accepts all strings in $L$ and rejects all strings not in $L$.

But what is a problem and how is a problem converted to language? What is an input for a problem? What is an acceptance problem?

there exists some Turing machine that halts on every input for that problem

I don't understand what this means.

Another example:

Definition: Given two languages $A$, $B$, we say $A \leq_p B$, or $A$ is polynomial-time reducible to $B$ if there exists a computable function $f: \Sigma^* \to \Sigma^*$ such that $w \in A$ if and only if $f(w) \in B$, and $f$ can be computed in polynomial time.

We have seen this same sort of idea with mapping reducibility in our last primer on Turing machines. Given a language B that we wanted to show as undecidable, we could show that if we had a Turing machine which decided B, we could solve the halting problem. This is precisely the same idea: given a solution for B and an input for A, we can construct in polynomial time an input for B, use a decider for B to solve it, and then output accordingly. The only new thing is that the conversion of the input must happen in polynomial time.

Again, what is an input for a problem for a Turing machine? What is a problem for a Turing machine?

  • $\begingroup$ checking if an addition $a+b = c$ is correct is decidable. you give $a,b,c$ as input to a TM and it outputs $1$ or $0$ depending if $a+b=c$ or not. If $a,b,c$ are written as binary numbers of size $N,M,L$ then the algorithm for checking if $a+b = c$ takes about $\max(N,M)$ bitwise operations, so its complexity is linear in the size of the input. $\endgroup$ – reuns Jul 16 '16 at 20:53
  • $\begingroup$ once you have the TM for checking the addition, you can also check the multiplication, by transforming the multiplication as many additions, and you can see that the multiplication reduces linearly to the addition. $\endgroup$ – reuns Jul 16 '16 at 20:57

A language means a set of strings, no more or less.

In this context a problem generally means a decision problem, which means a set of instances and a function from the set of instances to the set $\{Y,N\}$. Generally we require that each instance is described by a particular string, so a problem now becomes a function from some set of strings to $\{Y,N\}$.

In order to simplify things, and because it is usually not interestingly difficult to determine whether a given string encodes an instance of the problem at all, it is very common simply to ignore the fact that some strings don't describe problem instances, and instead arbitrarily require, for example, that all strings that don't describe instances map to $N$. So instead of this problem:

Input: A string that describes a graph.

Output: $Y$ if that graph has a Hamiltonian cycle, $N$ if it doesn't.

we're now talking about

Input: A string.

Output: $Y$ if that string describes a graph that has a Hamiltonian cycle; $N$ if it doesn't describe a graph, or describes a graph without any Hamiltonian cycle.

Now a problem is a function from the set of all strings to $\{Y,N\}$. And then, instead of a function we can equally view the problem as being defined by the set of all strings for which the correct answer is $Y$.

This is technically convenient because "the set of all strings for which the correct answer is $Y$" is a set of strings, which we have long time ago decided to call a language. So the techniques and terminology we have for dealing with sets of strings can be used to deal with problems too.

Formally "language" and "problems" are then exact synonyms -- each of them means some set of strings, and we're interested in finding procedures for determining whether a given string is a member of the set. Whether we call the set a "language" or a "problem" makes no difference.

Some other authors prefer not to completely ignore the fact that some strings may not describe instances of the problem we're intuitively thinking about. Those authors then need to hedge their definitions a bit -- for example saying that a Turing machine solves the problem if it behaves correctly when its input is a string that describes an instance of the problem, no matter how badly it behaves on input strings that don't.

This seems to be the case for your quote about "halts on every input for that problem".

  • $\begingroup$ Is a decision problem the same as what the author of the articles calls an acceptance problem? $\endgroup$ – CrabMan Jul 16 '16 at 21:05
  • $\begingroup$ And if a problem is "does the input graph have a hamiltonian cycle", then a string is an input to this problem iff it describes a graph. Is that right? $\endgroup$ – CrabMan Jul 16 '16 at 21:06
  • $\begingroup$ I think I understand both quotes in my question now. Thank you. I will mark this as an answer the next time I remember about it unless I find out that I still don't understand something. $\endgroup$ – CrabMan Jul 16 '16 at 21:12
  • $\begingroup$ "usually not interestingly difficult to determine whether a given string encodes an instance of the problem at all", so set of all meaningful strings should be decidable, Am I correct?? $\endgroup$ – Saravanan Nov 11 '18 at 12:43
  • $\begingroup$ @Saravanan: Yes, that will usually be tacitly assumed. $\endgroup$ – hmakholm left over Monica Nov 11 '18 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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