Log In
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Sep 2019
  1. Satbir

    567 Points

  2. Bikram

    566 Points


    348 Points

  4. Vimal Patel

    87 Points

  5. Shaik Masthan

    38 Points


    14 Points

  7. sekhar_1621

    13 Points

  8. OgbeborBeatrice

    13 Points

  9. RAMYA.F

    9 Points

  10. vkw1111

    9 Points

0 votes

I thought that algorithm satisfies the finiteness property.Means for every input it will stop after sometime. So I did P1 = P2.I am confused now.

in Theory of Computation 6 points 3 views
$P_1$ is the set of all Problems such that every problem has an algorithm and nothing is defined about the algorithm.

So we don’t know anything about the algorithm. i.e. $P_1$ could be thought as set of all algorithms.An algo may or may not halt.

$P_2$ is the set of all problems that have an algo that halts. i.e. $P_2$ could be thought as set of all algorithms that halts.

So obviously $P_2 \subset P_1$

Please log in or register to answer this question.