Tweeted twitter.com/#!/StackCompSci/status/287648411195437056
2 formating
source | link

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.

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

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

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

1
source | link

Decision problem and algorithm

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