[Solved]: Decision problem and algorithm

ignougroup
Problem Detail: I was reading about decision problem. I understand that decision problem tell yes/no answer for an input. The decision is based on a decision procedure also called an algorithm. The wikipedia says that

It is traditional to define the decision problem equivalently as: the set of inputs for which the problem returns yes. These inputs can be natural numbers, but may also be values of some other kind, such as strings over the binary alphabet ${0,1}$ or over some other finite set of symbols. The subset of strings for which the problem returns “yes” is a formal language, and often decision problems are defined in this way as formal languages.

Whether I can take it like algorithm written in a programming language defines the set of all possibilities and gives the output based on the input? So in computability theory, the problem should be encoded to some form? Is this same thing as the input tape and configuration of a Turing machine (set of 0’s and 1’s )?

Asked By : user5507

Answered By : Andrej Bauer

Traditionally, in computability theory all problems are encoded in terms of numbers, or sometimes strings of bits $0$ and $1$. This is a very “low level” kind of thing, it is like programming directly in machine code. The reason for doing this is mostly historic. Gödel originally encode first-order logic in terms of numbers to prove his incompleteness theorems. Similarly, if one approaches computability through recursive functions, it is natural to encode everything with numbers. And mathematicians just like numbers anyway. A computer scientist would recognize the benefits of using a more advanced programming language that supports datatypes. Programmers know that programming in machine code obscures a lot of ideas and makes everything technically difficult. Mathematicians know this too, but since they do not actually write code, just think about writing code, they do not appreciate this point of view sufficiently to switch from their traditional ways. So, to answer your question, here is a modern way of defining decision problems. Pick your favorite general-purpose programming language. Consider a datatype $D$ (can be numbers, lists, heaps, trees, whatever) and decompose the values into two disjoint sets $D_0$ and $D_1$, so that $D_0 cap D_1 = emptyset$ and $D_0 cup D_1 = D$. Observe that $D_1$ uniquely determines $D_0$ and vice versa, because $D_0 = D setminus D_1$. So we only have to specify $D_1$. Now, a decision problem $(D_0, D_1)$ is said to be decidable if there is a program $p : D to mathtt{bool}$ such that:

  1. $p$ is total, which means that $p(d)$ halts for every $d in D$,
  2. if $d in D_0$ then $p(d) = mathtt{false}$,
  3. if $d in D_1$ then $p(d) = mathtt{true}$.

All that stuff about encodings and finite words over an alphabet etc. is not necessary. It is only useful if you want to prove general theorems about arbitrary decision problems. But if you want to think about a specific decision problem, it is better to do it directly in your favorite programming language.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7786