cs3102 – Theory of Computation
计算机理论代写 You are encouraged to collaborate with up to 3 other students,but all work submitted must be your own independently written solution···
Collaboration Policy 计算机理论代写
You are encouraged to collaborate with up to 3 other students,but all work submitted must be your own independently written solution. List the names of all of your collaborators. Do not seek published solutions for any assignments. If you use any published resources when completing this assignment, be sure to cite them. Do not submit a solution that you are unable to explain orally to a member of the course staff.
Submission Format 计算机理论代写
Your submission to collab should be a single zip file containing:
- apdf of your written solutions
- thetex file used to generate that pdf
- allother items needed to generate the pdf from the tex file (images, )
problem 1 John Jacob Jingleheimer Schmidt
The following proof by induction claims to demonstrate that all people have the same name. This is clearly ridiculous. Explain the error in the proof.
Proof idea: show that for any set of people P, all people in that set have the same name. This is done by induction on the size of P.
Base Case: 计算机理论代写
when P = 1, clearly all people in the set P have the same name, as the one person will certainly have the same name as himself/herself.
Inductive Step: Assume that for arbitrary k N, people in any set of size k all have the same name (i.e. assume that if P = k then all people in set P have the same name). We can show that this implies all sets of size k + 1 contain people who have the same name (i.e. show if it holds that all sets P such that P = k contain only same-named people, then all sets P′ such that P′ = k contain only same-named people).
Consider a set P′ of size k + 1. Remove an arbitrary person x from P′. The remaining
people are not a set of size k, so they must all have the same name by the inductive hypothesis. Now replace x in the set and remove a different person y. The remaining people now form a set of size k, and so must all share the same name by the inductive hypothesis. This means that y’s name must match x’s name, as both of them shared the same name with all the other people in P′. This means that all people in the set P′ must have the same name.
problem 2 Nk is countable 计算机理论代写
For a set S, let Sk denote S Sk−1 where S1 = S (e.g. S3 = S S S) Show that k N we can conclude Nk is countable.
hint: you may want to use induction and dovetailing
problem 3 Powerset
Without using Induction, show that |2S | = 2|S| (hint: there are 2|S| strings in the language {0, 1}|S|).
njb2b h2-2
problem 4 Set of finite subsets
We know from class that for any countably infinite set S, it must be that 2S is not countable (i.e. the set of all subsets of S is uncountable). What if we restricted this to only finite subsets of S? I.e., is the set of all finite subsets of a countably infinite set S countable? Prove your answer.
problem 5 Non-finitely Describable Numbers 计算机理论代写
We showed in class that there are uncountably many real numbers. We also showed in class that there are only countably many numbers that can be described at all (since all descriptions can be written as strings, and there are countably many strings). This means that there are some real numbers which we cannot describe, we call these Non-finitely Describable Numbers.
One strange thing about non-finitely describable numbers is that although we know they exist, we can never come up with an example of one (by definition). Even without an example, we can still reason about them. This problem will ask you to prove things about non-finitely describable numbers, as being able to reason about things in the ab- stract (rather than generalizing examples) is a very useful skill to have for this course and beyond.
Prove or Disprove each of the following: 计算机理论代写
- Ifx is non-finitely describable, then −x must also be non-finitely describable
- Thesum of two non-finitely describable numbers must always be non-finitely de- scribable
- Theproduct of two non-finitely describable numbers must always be non-finitely describable
- Ifx is non-finitely describable, then x2 must also be non-finitely describable
problem 6 Infinite Strings
We stated in class that all strings we deal with will always have finite length. This problem will be the singular exception to that. If we can have finitely-long strings (strings may have countably-infinite length), is the set of all strings countable or uncountable? Prove your answer.
更多代写：CS代上网课 AI代考 assignment代写 会计论文代写 paper代写 计算机代写
