Member Avatar for chts12345

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?

  • 2 Contributors
  • 1 Reply
  • 168 Views
  • 4 Days Discussion Span
  • Latest Post Latest Post by Duoas
Member Avatar for Duoas

Your friend left out for statements...

If your Pascal program does not contain any looping constructs (loops, gotos, and recursion), then the halting problem is valid only if the program and/or the input is infinite.

To consider why, think about how a Turing machine's transitions are represented. Without loops, the transitions can never return to a node already visited. Hence, if such a program is finite, it must eventually stop.

Pascal has some implicit loops in routines like readln, etc. so even if the program is finite, if the input is infinite then it may never end.

Hope this helps.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.