Results 1 to 8 of 8

Math Help - Is Halting Problem valid for P?

  1. #1
    Newbie
    Joined
    Apr 2008
    Posts
    3

    Is Halting Problem valid for P?

    Hi All

    Here is my question

    "Let P be the class of all Pascal programs that don't use go to ,while and repeat statements, nor recursive procedure calls.Is Halting Problem Valid for P?"

    Now the interesting thing is that halting problem is valid if it has infinite loop and a program can not contain a loop until it has a recursive procedure like goto, while and for loop etc. So I think we can not get halting problem for P (the class of all Pascal programs) that don't use recursive procedure.

    But Still I have confusion in my mind. May be there exist a program which can contain infinite loop without using recursive procedure. I tried to find but I couldn't think any such program. So I want to know "Does anybody know any example in which halting problem is valid even if the program don't use loops and recursive procedure calls?"

    OR if you don't know any example then tell me what do you think about this problem. Is Halting Problem valid for P? If yes, Why?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by ajgargand View Post
    Hi All
    Here is my question
    "Let P be the class of all Pascal programs that don't use go to ,while and repeat statements, nor recursive procedure calls.Is Halting Problem Valid for P?"
    Now the interesting thing is that halting problem is valid if it has infinite loop and a program can not contain a loop until it has a recursive procedure like goto, while and for loop etc. So I think we can not get halting problem for P (the class of all Pascal programs) that don't use recursive procedure.
    Hello,

    The question, in Halting problem is, given a program and an input to the program, whether the program will eventually halt when run with that input.

    Without "go to ,while and repeat statements, nor recursive procedure calls", the program is an implementation of a linear algorithm. This type of program always proceeds forward, and thereby with finite lines of code, eventually WILL halt.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2008
    Posts
    3
    Quote Originally Posted by Isomorphism View Post
    Hello,

    The question, in Halting problem is, given a program and an input to the program, whether the program will eventually halt when run with that input.

    Without "go to ,while and repeat statements, nor recursive procedure calls", the program is an implementation of a linear algorithm. This type of program always proceeds forward, and thereby with finite lines of code, eventually WILL halt.
    Have a look at this program

    Code:
    var x,y:integer;
    var z:real;
    begin
      x:=22;
      y:=7;
      z:=x/y;
    
      writeln('z');
    end
    Output will be 22/7 which is Pi.
    22/7=3.14285142851428514285..................

    14285 repeat again and again and never halts.

    it is a linear algorithm but never halts.
    Last edited by CaptainBlack; April 27th 2008 at 05:43 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by ajgargand View Post
    writeln('z');
    end

    Output will be 22/7 which is Pi.
    22/7=3.14285142851428514285..................

    14285 repeat again and again and never halts.

    it is a linear algorithm but never halts.
    Hmm... this is dangerous.I am not Computer Science Engineer, so dont rely completely on my words. But this is what I think it is:

    The problem is while that the algorithm itself is linear, however the implementation is not. While you write "x/y", the machine level code will be executing a loop to compute the division. And that is why it goes to infinite loop.

    The Halting problem is a theoretical construct, which means your "algorithm" must never halt, not the implementation.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ajgargand View Post
    Have a look at this program

    Code:
    var x,y:integer;
    var z:real;
    begin
      x:=22;
      y:=7;
      z:=x/y;
     
      writeln('z');
    end
    Output will be 22/7 which is Pi.
    22/7=3.14285142851428514285..................

    14285 repeat again and again and never halts.

    it is a linear algorithm but never halts.
    1. \pi is not 22/7, 22/7 is a reasonably good approximation, often attributed to Archimedes.

    "The specific statement of Archimedes is Proposition 3 of his treatise Measurement of a Circle:
    The ratio of the circumference of any circle to its diameter is less than 3 1/7 but greater than 3 10/71"

    2. In Pascal the default float type is float4 a 32 bit float, and 22/7 will be rounded in whatever manner the machine specifies. There is nothing infinite about you program fragment, and it does halt, but with a 32 bit approximation to 22/7.

    RonL
    Last edited by CaptainBlack; April 27th 2008 at 05:44 AM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ajgargand View Post
    Hi All

    Here is my question

    "Let P be the class of all Pascal programs that don't use go to ,while and repeat statements, nor recursive procedure calls.Is Halting Problem Valid for P?"

    Now the interesting thing is that halting problem is valid if it has infinite loop and a program can not contain a loop until it has a recursive procedure like goto, while and for loop etc. So I think we can not get halting problem for P (the class of all Pascal programs) that don't use recursive procedure.

    But Still I have confusion in my mind. May be there exist a program which can contain infinite loop without using recursive procedure. I tried to find but I couldn't think any such program. So I want to know "Does anybody know any example in which halting problem is valid even if the program don't use loops and recursive procedure calls?"

    OR if you don't know any example then tell me what do you think about this problem. Is Halting Problem valid for P? If yes, Why?
    If the definition of Pascal does not allow the modification of the control variable in a for loop or case statement, then every finite Pascal program will halt. This is because every statement will be executed at most a finite number of times (under your restrictions).

    Now it is over 10 years since I wrote a line of Pascal so I can't guarantee that modification of control variables is forbidden (but it is in line with the phillosophy of Pascal that it is), but I would be prepared to bet on it.

    RonL
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Apr 2008
    Posts
    3
    Quote Originally Posted by CaptainBlack View Post
    If the definition of Pascal does not allow the modification of the control variable in a for loop or case statement, then every finite Pascal program will halt.

    RonL
    I also didn't use pascal for a long time so I am not sure that Pascal allow the modification of the control variable in a for loop or case statement.

    Is anybody sure that Pascal doesn't allow this kind of modification?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by ajgargand View Post
    I also didn't use pascal for a long time so I am not sure that Pascal allow the modification of the control variable in a for loop or case statement.

    Is anybody sure that Pascal doesn't allow this kind of modification?
    I should have been a bid more dogmatic about not being allowed to change a control variable inside a for loop in PASCAL. I know that I have used a language where changing the control variable is forbidden. PASCAL is the only language that this is a likely restriction, I know its not a restriction in Fortran versions 77 and earlier, and definately not in C.

    A quick check shows that it is indeed PASCAL which forbids the modification of the control variable inside the loop. However turbo-pascal (and presumably its derivative Delph) do allow the modification of the control variable.

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Blank tape halting problem help
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: July 1st 2011, 02:38 AM
  2. Halting problem reduction
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 27th 2009, 11:28 AM
  3. valid,non valid arguments
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 8th 2009, 06:12 PM
  4. Is this valid?
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 7th 2009, 05:38 AM
  5. Is this valid?
    Posted in the Calculus Forum
    Replies: 3
    Last Post: January 31st 2009, 04:28 PM

Search Tags


/mathhelpforum @mathhelpforum