(10) Show that the Post Correspondence Problem is undecidable over the binary alphabet S = {0,...

(10) Show that the Post Correspondence Problem is undecidable over the binary alphabet S = {0, 1}.

Expert Solution

Solution 10:

Proof method 1:

We can encode every string in a finite alphabet into a binary string (like a computer using binary to encode text). As PCP for a random alphabet is undecidable, a random encoding in binary is also undecidable.

Proof method 2:

Please give thumbsup, or do comment in case of any query. Thanks.

venereology answered 1 year ago

Let L be the set of all languages over alphabet {0}. Show that L is uncountable,...

Let L be the set of all languages over alphabet {0}. Show that L is uncountable, using a proof by diagonalization.

2. i. Consider a binary source alphabet where a symbol 0 is represented by 0 volt...

2. i. Consider a binary source alphabet where a symbol 0 is represented by 0 volt and a symbol 1 is represented by 1 volt. Assume these symbols are transmitted over a baseband channel having uniformly distributed noise with a probability density function: px= {18 for-4≤x≤4 0 Assume that the single decision threshold T is in the range of 0 and l volt. If the symbols 0 and 1 are sent with probabilities p0 and 1- p0 respectively, derive...

Problem 4 (Sets defined inductively) [30 marks] Consider the set S of strings over the alphabet...

Problem 4 (Sets defined inductively) [30 marks] Consider the set S of strings over the alphabet {a, b} defined inductively as follows: • Base case: the empty word λ and the word a belong to S • Inductive rule: if ω is a string of S then both ω b and ω b a belong to S as well. 1. Prove that if a string ω belongs to S, then ω does not have two or more consecutive a’s. 2....

An n-bit binary string is a sequence of length n over the alphabet {0,1}. How many...

An n-bit binary string is a sequence of length n over the alphabet {0,1}. How many n-bit binary strings are there? How many n-bit binary strings b1,…,bn are there such that b1b2≠00? In other words, how many n-bit binary strings don't begin with 00? How many n-bit binary strings b1,…,bn are there such that b1b2≠00 and b2b3≠11? How many n-bit binary strings b1,…,bn are there such that b1b2≠00 and such that b2b3≠01?

Suppose we restrict the domain of the Post correspondence problem to include only alphabets with exactly...

Suppose we restrict the domain of the Post correspondence problem to include only alphabets with exactly two symbols. Is the resulting correspondence problem decidable?

Show that the following problem i undecidable: Input: A Turing machine M. Output: Yes if M...

Show that the following problem i undecidable: Input: A Turing machine M. Output: Yes if M eventually halts when started on a blank tape, no otherwise Input: A Turing machine M and a tape symbol a. Output: Yes if M eventually writes a when started on an blank tape, no otherwise. Input: A Turing machine M. Output: Yes if M ever writes a nonblank symbol when started on a blank tape, No otherwise. Input: A Turing machine M and a...

Consider the language L1 over alphabet Σ = { 0, 1 } where the production rules...

Consider the language L1 over alphabet Σ = { 0, 1 } where the production rules for L1 are as follows: S → TT S → U T → 0T T → T0 T→ 1 U → 0U00 U → 1 Q → λ P → QU Transform this grammar into Chomsky Normal Form, consistent with the CNF specification in the Quick Reference, and using only Variables { S, T, U, V, W, X }. Implement that CNF grammar in...

prove Given two r.v’s X and Y over the same alphabet: (a) Show that the Kullback–Leibler...

prove Given two r.v’s X and Y over the same alphabet: (a) Show that the Kullback–Leibler distance D(P(X,Y) || P(X) P(Y)) = H(X) – H(X|Y) (b) Show that the bounds of Mutual Information (MI) are 0 ≤ I(X:Y) ≤ min [ H(X) , H(Y) ] with equality on the left if and only if X and Y are independent random variables, and with equality on the right if and only if either Y essentially determines X, or X essentially determines...

Given two r.v’s X and Y over the same alphabet: (a) Show that the Kullback–Leibler distance...

Given two r.v’s X and Y over the same alphabet: (a) Show that the Kullback–Leibler distance D(P(X,Y) || P(X) P(Y)) = H(X) – H(X|Y) (b) Show that the bounds of Mutual Information (MI) are 0 ≤ I(X:Y) ≤ min [ H(X) , H(Y) ] with equality on the left if and only if X and Y are independent random variables, and with equality on the right if and only if either Y essentially determines X, or X essentially determines Y...

The Following Java expression: S/10 * 10 + 10 – S = C Show that this...

The Following Java expression: S/10 * 10 + 10 – S = C Show that this expression gives a value of 2 when S contains the int value 78. You must show every step in your working, performing exactly one operation on each line. I have tried to no end to make sense of this and I know there is an order of precedence in the operators but I can't make any sense of it. Could someone please explain this...

Question