In Lesson 1 we described the Turing machine model to answer the question, "What is a computer?" The next question is "What can we compute?" First we need some definitions to describe problems to be computed.

First we need an *alphabet* which we denote Σ. Any finite
Σ would work; for most of complexity we assume that Σ =
{0,1}. Machines take as inputs words or *strings* consisting of a
finite sequence of alphabet symbols or characters. Examples: 0101,
000, 1101100. The length of the string is the number of characters in
the string. We use ε to represent the special string with zero
characters.

A language is set of strings. It could be finite or infinite. Examples include

- {ε,0,1,001}
- The set of strings of odd length
- {1,10,110,1110,11110,...}

^{*}to represent the set of all strings and ∅ to represent the empty set of no elements. Note the difference between the empty set of strings and {ε}, the set consisting of the single string of length zero.

A *class* is a set of languages. Examples of classes include

- The class of all finite languages.
- The class of all languages containing the string ε.
- The class of all languages that are subsets of {0,1,00,11,101}.

*complexity class*is a special kind of class based on resource-bounded Turing machines. We will come back to complexity classes in a later lesson.

Consider a Turing machine M on some input string x which we denote M(x). We will focus on two possible outputs "yes" or "no". This yields three possibilities for M(x).

- M(x) outputs "yes" in which case we say M(x)
*accepts*. - M(x) outputs "no" in which case we say M(x)
*rejects*. - M(x) does not halt.

*total*.

The class of *computably enumerable* languages is the set of languages L
such that L = L(M) for some Turing machine M. You might see
*recognizable* or *recursively enumerable* as other names
for the computably enumerable languages.

The class of *computable* languages consists of the set of
languages L such that L = L(M) for some total Turing machine M. You
might see *decidable* or *recursive* as other names for the
computable languages.

Can you please elaborate the difference between recognizable and decidable languages.

ReplyDeleterecognizable languages can be accepted by some turing machine, but if an input string is not a member of the language, they will either reject or loop forever, never halting. Decidable languages are a subset of the recognizable languages, the difference being that not only can they be accepted by some turing machine, if an input string is not a member of the language then it will definitely reject. Decidable languages never loop forever.

ReplyDelete