# Can all types of computational problems be modeled as decision problems?

Can all types of computational problems (search, counting, optimization...) be modeled as (sets of) decision problems? Rephrased: For every type of computational problem is there a set of decision problems that if you solve those problems you get the result of the original problem?

Decision problems can be modeled as word to language membership. On the surface, this only models the functions that go from f:{0,1} * -->1 not all the other types of functions. Some g: {0,1} * -->{0,1} * for example. But I have a feeling the answer could be yes...

Yes. Every computation problem can be viewed as computing a function $$f:\{0,1\}^ \to \{0,1\}^*$$: on input $$x$$, the algorithm outputs $$f(x)$$.
Here is a corresponding decision problem: given $$x$$ and $$i$$, determine whether the $$i$$th bit of $$f(x)$$ is 1. If you can solve that decision problem, you can solve the original computation problem.
(Strictly speaking, you also need a way to decide whether the length of $$f(x)$$ is $$i$$; that can be addressed by defining the decision problem as taking inputs $$x,i,b$$; if $$b=0$$, then the problem is to determine whether the $$i$$th bit of $$f(x)$$ is 1; if $$b=1$$, the problem is to determine whether the length of $$f(x)$$ is $$i$$.)