Please help me with some cipher's exercise and Kryptographie

Apr 2016
13
0
Bulgaria
1 / Consider the following version of Post’s Correspondence
Problem. For a finite set of symbols Σ the input lists a1, . . . , as and b1, . . . , bs both
only consist of sequences of length 1 with elements from Σ.
Can this version be solved efficiently by an algorithm?

2 / Show that the set {0, 1, 2}∗ of all finite 0, 1, 2-sequences is countable. Is the set N∗ = {0, 1, 2, . . .}∗ also a countable set?

3/ Prove the following statement by using a diagonal argument:
Let X be a set. Then there is no surjective map f from X to the power set P(X).
Hint: Consider the subset Y ⊆ X with Y := {x ∈ X | x /∈ f(x)}.

Please people try to solve these.. If you have any solution please help me..
 
Apr 2016
13
0
Bulgaria
Thats all I have in my exerceise list..
 

mathman

Forum Staff
May 2007
6,932
774
1. I have not taken this course, so I don't know what Post's correspondence problem is.

2. What is the significance of * in the set description?
 
Similar Math Discussions Math Forum Date
Probability and Statistics
General Math
General Math
Calculus