Practice problems on Mapping Reducibility

November 13, 2010 1 Comment

Let alphabet set be \Sigma. Given two languages A,B \subseteq \Sigma^*. A is said to be mapping reducible to B if there exists a Turing computable function f s.t. \forall x \in \Sigma^*,~ x \in A \Leftrightarrow f(x) \in B. When A is mapping reducible to B, we denote it as A \leq_m B, A \not \leq_m B otherwise.
In this post I mention a few practice problems on mapping reducibility, a subset of which were posed to the students of ics211 in 2009, Monsoon and cs3105 in 2010, Spring.

Consider the following languages :-

  1. L_1 = \{ < M,w > | M accepts w\}
  2. L_2 = \{ < M > | L(M) \neq \phi \}
  3. L_3 = \{ < M_1,M_2 > | L(M_1) \cap L(M_2) \neq \phi \}
  4. L_4 = \{ < M > | L(M) = \Sigma^{*} \}
  5. L_5 = \{ < M > | L(M) = \{0^{n}1^{n}|n > 0\}\}
  6. L_6 = \{ < M_1,M_2 > | L(M_1)=L(M_2)\}
  7. L_7 = \{ < M_1,M_2 > | L(M_1)=\overline{L(M_2)}\}

In the languages mentioned above M,M_{1},M_{2} donote a Turing Machine.
Prove the following :-

  1. \forall i \in \{1,2,3\} ~ \forall j \in \{1,2,3,4,5,6,7\}, L_i \leq_m L_j.
  2. \forall i,j \in \{4,5,6,7\}, L_i \leq_m L_j.
  3. \forall i \in \{4,5,6,7\} ~ \forall j \in \{1,2,3\}, L_i \not \leq_m L_j.

Filed under puzzle, theoretical computer science

Godel’s Second Incompleteness Theorem

July 29, 2010 2 Comments

A formal system is characterized by its axiom set. In this post, I talk about systems with only finitely many axioms. A system is said to be consistent if its axioms do not contradict any of its axioms. In a system, a statement is said to be independent of the system if it is not derivable from its axioms logically.

Godel’s Second Incompleteness Theorem states: If a system is consistent, then the consistency of the system is not provable within the system.
More formally one may state the theorem as: If a system S is consistent, then the proof of the statement “S is consistent” is independent of S.

It follows that, if there is a proof of consistency of a system within the system then it is necessarily inconsistent ( contra positive of the theorem statement ). The surprise element related to this theorem is, say some postulates such as Euclid’s postulates to do 2-d geometry are consistent, then this very fact forbids us from giving a proof of postulates being consistent. One may think of proving consistency of a system S by moving to a higher system S', but then the consistency of S relies on the consistency of S', and the problem of proving consistency of S remains as such.

A related puzzle problem,
Consider a system S with just one axiom, A: 0 is a number.
Consistency proof:-
Since nothing is derivable with just one axiom, hence the only axiom A does not contradict itself. Hence, S is a consistent system.

S is consistent and we have a consistency proof for S. too.
Isn’t this a counter example to Second Incompleteness Theorem? Why not ?

Filed under puzzle, theoretical computer science

A Buggy Argument to #real numbers = #natural numbers

July 21, 2010 4 Comments

A real line is a line whose points correspond to real numbers.
1. Let N_1 be the number of points on a real line
2. Let N_2 be the number of points in [-1,1] interval over a real line.
3. Let N_3 be the number of points in (-1,1) interval over a real line.
4. Let N_4 be the number of points in a unit square.

N_1 seem to be infinitely greater than N_2 and N_2 seem to be some twoish greater than N_3. N_4 seem to be quite a lot bigger than N_3. Georg Cantor created a paradise, a theory of sets which suggests N_1 = N_2 = N_3 = N_4. Now this is something hard to digest at the first sight, but that’s the way it is.

Later on, Russell proved that the Cantor’s theory of sets is inconsistent i.e. it’s axioms are self-contradictory. This doesn’t mean that the above mentioned equalities do not hold, one may use ZFC theory of sets ( which is immune to various paradoxes which Cantor’s theory faced ) to arrive at the same result. Though ZFC hasn’t witnessed a paradox yet and is widely believed to be consistent, we still do not know whether it is a consistent theory of sets or not since Godel‘s second incompleteness theorem states that the consistency of a formal system S can be proved within the system only if it is inconsistent ( or equivalently we can say that if a system is consistency then it’s consistency can not be proved within the system) and hence forbids us from proving the consistency of ZFC within ZFC.

Let \mathbb{N} be the set of natural numbers and M be the set of all the subsets \mathbb{N}. Cantor proved that |\mathbb{N}| < |M|. With this proof he also contributed a technique known as Diagonalization, very useful tool in theoretical computer science.
Other day I was playing with the sets, \mathbb{N}, M and arrived at a mapping f:\mathbb{N} \rightarrow M as described below. One may trivially show that f^{-1} exists and hence f is a bijection between \mathbb{N} and M ( i.e. |\mathbb{N}| = |M| )!!

Description of f:
i=1;n=1;
while(1) {

  • A be the set of all those set S \subseteq \mathbb{N} with \displaystyle\sum_{s \in S}s=i;
  • for each Z \in A{

    • map Z to n;
    • n++;

    }

  • i++;

}

Few example mapping by the function f:-
{1}->1,
{2}->2,
{1,2}->3, {3}->4,
{1,3}->5, {4}->6,
{2,3}->7, {1,4}->8, {5}->9,
{1,5}->10, {2,4}->11, {1,2,3}->12, {6}->13,
{1,6}->14, \ldots

Now given that Cantor gave a clean proof for |\mathbb{N} < |M|, something has to be wrong with argument given above which claims |\mathbb{N}| = |M|. What is it?
Note that I have detailed f as an infinite loop mapping. One may instead detail f as a function which takes a set Z as input and outputs f(Z), a natural number.

PS: You can post your doubts/comments/solutions in the comments section or mail them to me.

Filed under puzzle, theoretical computer science

A Special Case of Hilbert’s Tenth Problem

July 19, 2010 6 Comments

In 1900, David Hilbert posed a list of 23 quality problems in mathematics, many of them remain unsolved till date. These problems have caused a significant progress in various disciplines of mathematics. Briefings and current status of the problems can be found here. In this post, I am going to brief Hilbert’s Tenth Problem and pose a related puzzle problem.

A root of a multivariate polynomial p(x_1,x_2,\ldots,x_n) are values of variables x_1,x_2,\ldots,x_n at which p vanishes to 0. Hilbert in his 10th problem asked for an algorithm for the following decision problem: Given a multivariate polynomial with integral coefficients as input, if there are any integral roots to it. (For example, p(x,y)=x^2y^2+x-2 has integral roots and p(x,y,z)=2x^2+2y^2+2z^2-1 has no integral roots.)

In 1970, Yuri Matijasevic proved that there can not exist an algorithm for the problem. But what about the special case when the input polynomials are univariate only i.e. Does there exist an algorithm which when given a univariate polynomial with integral coefficients as input tells if at all there are any integral root to it? If yes, then what would be the best possible algorithm for this with respect to time complexity ( i.e. the number of steps it takes to arrive at the answer (yes/no) on the worst case input to your algorithm).

PS: People can post their (full/partial) solutions in the comments section.

Filed under puzzle, theoretical computer science

Follow

Get every new post delivered to your Inbox.