Decidability and reducibility Flashcards
explain the claim :
There are more problems than languages can solve them
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
explain cardinality and countable sets
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
explain the set of the subset is uncountable
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
prove that There are more languages than problems to solve them
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
There are languages that not turing machine recognizable
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
The undecidability of ATM problem
ATM problem : {(, w) | M is a turning machine and and M accepts W }
prove Atm in RE
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
prove ATM no-in R
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
A language A is decidable if it is Turing recognizable and co turning recognizable
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
What is the Church-Turing thesis? Give arguments in favor of it.
Intuitive notion of algorithm equals Turing machines algorithms
give an example of the encoding of the problem
for example, this problem can be encoded as :
the input is the binary representation of the
what are decision problems
they are problems that require a yes no result
define a problem
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
what is a Turing machine
it is a set of states with a tape
define RE recursively enumerable language
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
define the class R
R is the set of decidable language, which means
for a language L, TM manages to halts on it
every Multi tape Turing machine has an equivalent single tape turning machine
because simple tapes can be gathered into a single tape
explain DTM = NDTM
DTM can be simulated on NDTM branches using breadth-first search
what is an enumerator
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
prove that a language is Turing recognizable if some TM recognizes it
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
