# Thread: Is Halting Problem valid for P?

1. ## 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?

2. Originally Posted by ajgargand
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.

3. Originally Posted by Isomorphism
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.

4. Originally Posted by ajgargand
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.

5. Originally Posted by ajgargand
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

6. Originally Posted by ajgargand
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

7. Originally Posted by CaptainBlack
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?

8. Originally Posted by ajgargand
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