Question 1 - True or False. a- The set of (TM M, input s, integer k > 0) triplet

a) True b) True c) True e) Ture f) False h) True ( L is decidable means L is recursive) i) False j) True k) True L) True n) True o) Flase

ID: 3920480 • Letter: Q

Question

Question 1 - True or False.

a- The set of (TM M, input s, integer k > 0) triplets such that M halts on s within k steps are TM decidable.

b- The Church-Turing Thesis says that every language can be recognized by some TM.

c- A busy beaver is a TM that writes an infinite number of 1's with the fewest possible states.

d- The following TM program loops forever when we start with an empty (and infinite) tape.

1,_,2,X,>

2,X,1,_,<

e- The set of TM machines is countable.

f- The language of (TM M, input s) pairs such that M halts on s is not TM decidable.

g- A TM may have an infinite number of states as long as the set of states is countable.

h- If L is decidable then L complement is decidable.

i - The set of languages over {0,1} is countable.

j- A nondeterministic TM can be simulated by a deterministic TM.

k - Every multitape TM can be simulated by a single tape TM.

L - If L is TM recognizable and L-complement is TM recognizable then L is decidable.

m - Some infinite sets are not countable.

n - There exists a one-to-one function from the set of real numbers to the set of natural numbers.

o - Every language L is such that either L is TM recognizable or the complement of L is TM recognizable.

a) True

b) True

c) True

e) Ture

f) False

h) True ( L is decidable means L is recursive)

i) False

j) True

k) True

L) True

n) True

o) Flase

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.