Assignment on Decidability and Undecidability in TCS

This homework assignment explores several core concepts in theoretical computer science, specifically focusing on decidability and undecidability. The solution addresses four distinct problems. The first problem examines a language of binary numbers that are powers of 2 and determines its decidability. The second problem analyzes a language related to looping behavior of Turing machines and whether it is semi-decidable. The third problem investigates the decidability of a language involving Turing machines that reject a specific string and halt on another string. The final problem deals with a language where a Turing machine accepts a string without moving to a blank cell. Each problem involves analyzing the language's properties and proving decidability or undecidability using techniques like reductions and the halting problem.

University ******
Semester ******
Student Id ****
Student Name ***
Submission Date ****
1

1. Question 1
a . Apower = { ¿<m> ¿ } Is the language of the M consists of the binary number which is the power of
2, where
M is the determine on the binary number of language
∑ ¿ { 0,1 }2
‘M’ is recognizing if the language of L is accepting all the binary number of the strings on L.
Let us consider the binary number is M (L) = { 0i 1i /¿I is the power of 2} The binary number of
the languages consists of L1 and L2. The language of L1 consists of the all the encodings at the
same time L2 consists of all the accessing of all the prime numbers (Atallah and Blanton,
2010). The given strings consists of the 0 ∩1 which contains the binary number which are in
both languages and is the encoding of ATM , are primes when viewed as binary numbers. The
language is decidable.
b. Aloop2 = {< M >| M, |M loops on some string of length at least 2 }
Let M be the number of states in M. And K is the size of alphabets that M users, and r=|
w|. If M uses than the maximum of the string length is 2, then that is the maximum length of
the strings. The language is neither semi-decidable nor co-semi-decidable there are using the
two reductions of the strings (Atallah and Blanton, 2010). Quantifiers and verifiers (use VA,
VR, and VH for checking that a computation is accepting, rejecting and halting,
respectively). The language definition of the quantifiers can be performed on the extension is
the verifier characterization of the semi decidable. Let us use ATM as the hard problem of the
reduction quantifiers to show that the string Aloop2 is not co semi decidable. We will reduce
a not co-semi-decidable by using ATM to Aloop2. Then to show that L02 is not a semi
decidable, we will reduce a non-semi decidable ⃗ ATM to L02 . First to find the string length ifL02
is the non-semi-decidable by showing that⃗ ATM ≤ m L02. The computable function of the
definition reduction is F ((M, w)) =<M'> that for the pair of the string length is M, w
contracts M, M|M if the strings accepts M loops on 2 and at the same time it accepts 1. We
are reducing if a semi decidable language is the verified quantifier. We will force M to
always loop on 2 and will make its behaviours on 2 depend on whether M accepts the string
length of 2.
2

M: on input Aloop2
For Aloop2=0, Aloop2=1 it does not matter to find the string length is M
It could accept, or run M is L02, anything, suppose M is rejected (Auger and Doerr,
2011).
If Aloop2=2 then loop
If Aloop2= 1 then run M on L02
If M accepts, than the string is accepted.
If M rejects, than loop (here, reject would also be correct).
c.The Halt01 = {< M >| M rejects string “1” and halts on some string ending with 0}.
Halt01 can consist of the two strings on 0, 1. Let us consider the ending of the stings is 0
and rejecting of the string is 1. It is possible to define the string of the producing as an output.
In that case, the computation halts in a rejecting state with 1, except for the output and head
pointing of the first output. The Halt01 of the string can be used for the two methods, i.e
accepts and rejects. The Halt01 string can be ending with 0. Let us show that the ATM is not
decidable. Assume for the sake of contradiction that it is so, there of the computation H that
takes as an input i <M>|M and halts rejecting the string in 1.
ATM ≤ Halt 01
Let us x∈∑ x¿
, and assume the x=<M>|M, where M is the computation quantifier.
F(x) =<M> is the contradiction of the computation.
M: on the input A
Write 0, 1 on the tape
Simulate M running on input 0, 1
IF and when M halts and rejects <M> halt with rejects the 1
IF and when M halts and end <M> halt with ending with 0
It is also to see the that 0, 1 ∈ ATM ∈Halt01. Since is the string is M ∈ reject( 1) and M∈ end ¿
)
3

d. Ain = {< M, w > |M accepts w without moving to a blank cell}.
We will show that, {< M, w > |M} is the computation. F(x) =<M> where M follows on
Blank cell taps(w).
M: on input x'
Write w on the tape
Simulate M running on input w; if and when M halts and accepts,
M0 halts and accepts;
If and when M halts and rejects, M0 goes into an infinite loop.
Clearly f is computable. It is also easy to see that x ∈ ATM ⇔ f(x) ∈ blank cell, since
M accepts w ⇔ M halts on blank cell.
4

References
Atallah, M. and Blanton, M. (2010). Algorithms and theory of computation handbook.
Boca Raton: CRC Press.
Atallah, M. and Blanton, M. (2010). Algorithms and theory of computation handbook.
Boca Raton, FL: Chapman & Hall/CRC.
Auger, A. and Doerr, B. (2011). Theory of randomized search heuristics. Hackensack,
N.J.: World Scientific.
5