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.