Decidability and reducibility

Question 1

explain the claim :

There are more problems than languages can solve them

Answer 1

languages : l’ = {L | L in 2^Σ *}
problems : M’= { M | M is DTM that halts on every input}
since both l’ and M’ are infinit then cardinality can be used to compare their sizes

Question 2

explain cardinality and countable sets

Answer 2

cardinality is equivalence relation between sets, bijection
countable set is the set that has cardinality with N0
when e say two sets do not have bijection with each other means the two numbers do not have the same cardinality

Question 3

explain the set of the subset is uncountable

Answer 3

through constructing a table composed of (2^A in term of A) through diagonalization, a new set is obtained such that :
S : {ai | ai not-int Si } , ∀ i in N S not-int Si
hence no bijection is obtained with N, eventually set of subset is infinite

Question 4

prove that There are more languages than problems to solve them

Answer 4

Knowing that the set of Turing machine is countable since there exists a bijection between it and the N set and the set of subset is not countable eventually 2^Σ * (set of
languages of finite words on a finite alphabet)is not countable
hence there are more language that problems to solve them

Question 5

There are languages that not turing machine recognizable

Answer 5

a table is constructed such that :
enumeration of elements in Σ *
in term of the enumeration of DTM
through diagonalization element wi not-in L(Mj) with with this contradiction we can conclude that there are languages that are not Turing machine recognizable

Question 6

The undecidability of ATM problem

Answer 6

ATM problem : {(, w) | M is a turning machine and and M accepts W }

Question 7

prove Atm in RE

Answer 7

we simulate M on w, if w in L(m) we know that this is an accepting state, to enumerate ATM, we should :

enumerate set of TM M0...Mn 
enumerate set of words W0...Wn
enumerate set of steps N 
once getting (M,w,n), we run M on w till reaching the accepting state

Question 8

prove ATM no-in R

Answer 8

Initially, we run H on M and do whatever it does
then we set up TM D such that outputs the reverse of H
we Run D on itself consequently we obtain a contradicton

Question 9

A language A is decidable if it is Turing recognizable and co turning recognizable

Answer 9

the complement of Atm is not turning recognizable, if we assume that co-Atm is turning recognizable then as it is Atm then we should also assume that that ATM is decidable and that’s not the case

Question 10

What is the Church-Turing thesis? Give arguments in favor of it.

Answer 10

Intuitive notion of algorithm equals Turing machines algorithms

Question 11

give an example of the encoding of the problem

Answer 11

for example, this problem can be encoded as :

the input is the binary representation of the

Question 12

what are decision problems

Answer 12

they are problems that require a yes no result

Question 13

define a problem

Answer 13

a problem means solve something that is equivalent to where w in L
which can be formalized by the set of finite words over finite alphabit

Question 14

what is a Turing machine

Answer 14

it is a set of states with a tape

Question 15

define RE recursively enumerable language

Answer 15

Let L(M) a language that is accepted by TM, such that for each w in L, M has an accepting state on it

Turing recognizable TM is language such that L(M) = L

Question 16

define the class R

Answer 16

R is the set of decidable language, which means

for a language L, TM manages to halts on it

Question 17

every Multi tape Turing machine has an equivalent single tape turning machine

Answer 17

because simple tapes can be gathered into a single tape

Question 18

explain DTM = NDTM

Answer 18

DTM can be simulated on NDTM branches using breadth-first search

Question 19

what is an enumerator

Answer 19

an enumerator is simply a Turing machine with a printer :
an enumeration of L is given such that
for each w in L there exit i such that E(i) = L
and the union of E(i) ==> L

Question 20

prove that a language is Turing recognizable if some TM recognizes it

Answer 20

First, let E be an enumerator for the language L. We construct a Turing
machine M that will behave on w as follows:
1) Start E. Each time that E writes a word, compare it to w.
2) If w appears, we stop and accept.
Clearly L(M)=L.
Let M be a Turing machine that accepts L, we construct the enumerator E
as follows. First, let s1 s2 s3 … si … be the list of possible finite words on the
alphabet of L. The enumerator E behaves as follows:
repeat the following instructions for i=1,2,3,…
A) execute M for i steps on the inputs s1,s2,…,si.
B) if one of the executions accepts, write the corresponding sj