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.
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?