1. Suppose that S is an infinite countable set, then prove that the power-set 25 of...

Transcribed Image Text:

1. Suppose that S is an infinite countable set, then prove that the power-set 25 of S is uncountable. (hint: use diagonalization) (5 pts) 2. Prove that the set of strings S={(a, b, c}* is countable.(hint: use diagonalization) (5 pts) 3. Prove that the halting problem is unsolvable (undecidable). (hint: use diagonalization) (5 pts) 4. State-entry problem: Given a turing machine, an input string and a state in that turing machine, tell whether the turing machine will enter to that state or not during the executing of the input string. Prove that the state-entry problem is unsolvable (undecidable). (hint: use reduction) (5 pts) 1. Suppose that S is an infinite countable set, then prove that the power-set 25 of S is uncountable. (hint: use diagonalization) (5 pts) 2. Prove that the set of strings S={(a, b, c}* is countable.(hint: use diagonalization) (5 pts) 3. Prove that the halting problem is unsolvable (undecidable). (hint: use diagonalization) (5 pts) 4. State-entry problem: Given a turing machine, an input string and a state in that turing machine, tell whether the turing machine will enter to that state or not during the executing of the input string. Prove that the state-entry problem is unsolvable (undecidable). (hint: use reduction) (5 pts)

Answer rating: 100% (QA)

The image contains a set of four questions each related to topics in set theory and theoretical computer science Here I will address each question in order 1 Suppose that S is an infinite countable se... View the full answer