## Is Halting Problem Valid for P?

Hi All

I was discussing halting halting problem with one of my friend yesterday. He asked me a good question. Here is the 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?

## Comment viewing options

### Are there any pascal

Are there any pascal compilers that support infinitely long source files?

;-)

### Goto considered harmful

Dijkstra's essay shows how goto can be modelled using procedure calls.

### GEB

The book "Godel, Escher, Bach: An Eternal Golden Braid" by Douglas R. Hofstadter has some discussion of three programming languages, called BlooP, FlooP, and GlooP. According to (what I remember of) that discussion, if you don't have recursion or while loops or something like that, you can't get an infinite loop.

### It depends what you mean by ...

... "Something like that". Early versions of Pascal did not require the full header of a function or procedure in a parameter position. Compilers happily accepted things like

procedure p (procedure q)
begin
q(q)
end;


To get the infinite loop needed for the halting problem, just write

  p(p)


It's harder to write this if you have to provide a type for p.

### The loop-hole

The problem statement didn't forbid "for"

program forever;
var
i:integer;
begin
for i:= 1 to 10 do
begin
i:=1;
writeln('help, I am stuck');
end;
end.


### I don't think for-loop is a hole...

IIRC you can't modify the loop variable in a Pascal for-loop.

### It worked on

It worked on CodeIDE. That doesn't mean it would work in all Pascal variants, of course.

Edit: poking around Google shows that Pascal variants generally do not allow you to muck with index variables. So if we assume that "P" follows this restriction my loophole is closed.

### It sounds like the OP meant

It sounds like the OP meant something like a language that only allows looping for a fixed (when the loop is entered) number of iterations. IIRC that boils down to only allowing primitive recursion, and, indeed, such programs always halt. There's also a large family of functions that can't expressed that way, such as Ackermann. In day to day programming, that's probably not such an issue.

I do not know Pascel. Is there any conversion of the following program to Pascel.

function P(){
Q();
}

function Q(){
P();
}

It can be generized as -
"An unsafe procedure call loop: P1->P2->...->Pn->Pi s.t. i

### No recursion

There is a direct Pascal translation of that - Pascal is very similar to C in a lot of ways. But the OP said no recursion. Think old school Fortran or Cobol. Modern variants of these languages do allow recursion, but older variants did not create an activation record on each entry to a function. Instead, a function had a single statically allocated spot for its variables. Any attempt to reenter a function from within its own call environment would cause an error at runtime.

### There's also a large family

There's also a large family of functions that can't expressed that way, such as Ackermann.

Yes, they can (given higher order functions).

### No they can't

...and that paper does not make the claim that they can. The author points out that a restricted subset of the Recursive functions are sufficient to do all of the potentially non-terminating things that we would want, while allowing proof of termination. He does NOT under any circumstances show that we can embed Recursive functions into a language only allowing Primitive Recursion.

The Ackerman example uses full Recursion that is guarded by the property that each subcase must compute a lesser parameter in some well-founded ordering. This is a standard syntactic trick used in Termination Analysis that has been used to guide the language definition.

Another (non-related) issue that I seem to remember about that paper is that he uses a potentially infinite amount of codata which did seem to be cheating a little, at the time.

As far as the original forum post goes; somebody earlier pointed out that Pascal doesn't allow overwriting loop indices. Given that the set described contained straight-line-code and static repetitions of it - the halting problem is trivially true for the set.

### The paper makes the claim

The paper makes the claim that Ackerman can indeed be shown to terminate. This whole thread is about functions which can be shown to terminate, and I was clarifying that a class of non-primitively recursive functions like Ackerman can also be shown to terminate.

I think that you've misread the comment that you replied to slightly. The context of the part that you quoted was "IIRC that boils down to only allowing primitive recursion, and, indeed, such programs always halt". The class of functions that you then refered to in context was not those that terminate, but those that are primitive recursive.

Specifically Ackermann was referred to as an example of something that was non-primitive recursion, not something that didn't terminate.

### Problemless, useless

You language as described does not suffer from the halting problem, but this does not 'break' the Halting Problem or anything like that since it is only defined on turing-complete languages. While your language has the nice property of provable termination, it has the rather undesirable side-effect of not being able to work on data of arbitrary length. It's the basic Godel trade-off

### related question

This is reminiscent of the oft-asked question:

Ich bin Ersti und studiere Informatik. KÃ¶nnt ihr mir mal bitte kurz erklÃ¤ren was eine if-Schleife sein soll. In unserem C-Kurs kam da letztens so eine Thema auf und ich konnte damit gar nichts anfangen.

### What is it you're asking, exactly?

What do you mean by "valid"?

### Maybe this will help...

I think his question was slightly confusing because he's talking about the halting problem, but is really only interested in whether or not any program exists which doesn't halt. To clarify, if we let NP be the class of program that can be written in Normal Pascal, and choose a suitable equivalence relation '=', then I think he's essentially asking whether P = NP.

It's been established that P=NP. This link has a video with an explanation of the proof.

### Chomsky Hierarchy

Hello ajgargand,

If you restrict a language so that it does not use infinite loops or general recursion (i.e., without some "countdown" parameter limiting the depth of recursive calls), it moves down a rung in the Chomsky Hierarchy from "Turing-complete" to "context sensitive." In context sensitive languages, the halting problem is apparently PSPACE-complete -- decidable, that is, but not terribly practical.

I believe Coq is effectively context-sensitive as well -- in that recursive function calls require a parameter of decreasing structure, which seems isomorphic to a foreach loop -- and it is due to this quality that we are able to prove all sorts of things about code written in Coq.

Or, I could be way off. Correct away, folks.

### Unless you've missed part of

Unless you've missed part of the description that you meant the halting problem is trivial for that class of language. If every recursion is guarded by a decrease on a well-founded ordering then the class of recursions is equivalent to bounded loops - so every program trivally terminates. Or do you mean something else by "countdown parameter" ?

### Don't forget to check out the classic paper

On Folk Theorems by David Harel which discusses the theorem

Every flowchart is equivalent to a while-program with one occurrence of while-do, provided additional variables are allowed

but more importantly is about what is involved in making such a statement actually a theorem.