4.1 DECIDABLE LANGUAGES (Ákvarðanleiki) & 4.2 UNDECIDABILITY

Question 1

We chose to represent various computational problems by languages, why is that?

Answer 1

Because we have already set up terminology for dealing with languages.

Question 2

Decidable languages are

Answer 2

Recursive languages (Halts every time, accepts or rejects)

Question 3

Every context-free language is decidable.

Question 4

What is undecidability about?

Answer 4

There is a specific problem that is algorithmically unsolvable. Computers appear to be so powerful that you may believe that all problems will eventually yield to them. The theorem presented here demon- strates that computers are limited in a fundamental way.

Question 5

What is the universal Turing machine first proposed by Alan Turing in 1936?

Answer 5

It is capable of simulating any other Turing machine from the description of that machine. The universal Turing machine played an important early role in the development of stored-program computers.

Question 6

What is Diagonalization method?

Answer 6

The proof of the undecidability of ATM uses a technique called diagonalization, discovered by mathematician Georg Cantor in 1873.

Question 7

How does diagonalization work?

Answer 7

Two finite sets have the same size if the elements of one set can be paired with the elements of the other set. This method compares the sizes without resorting to counting. We can extend this idea to infinite sets.

Question 8

A set A is countable if either it is finite or it has the same size as N .

Question 9

However, for some infinite sets, no correspondence with N exists. These sets are simply too big. Such sets are called uncountable. Cantor proved that what is uncountable ?

Answer 9

Cantor proved that R(real numbers) is uncountable. In doing so, he introduced the diagonalization method.

Question 10

Some languages are not Turing-recognizable. Why ?

Answer 10

Because each Turing machine can recognize a single language and there are more languages than Turing machines, some languages are not recognized by any Turing machine.

Question 11

We say that a language is co- Turing-recognizable if it is ?

Answer 11

the complement of a Turing-recognizable language.

Question 12

for any undecidable language, either it not Turing-recognizable or ?

Answer 12

or its complement is not Turing-recognizable

Question 13

A language is decidable if it is Turing-recognizable and co-Turing-recognizable.

Answer 13

In other words, a language is decidable exactly when both it and its complement are Turing-recognizable.