CODEWITHSUNDEEP
pythonhalting-problem
Kyle
Kyle

Reputation: 154

How do I avoid non-halting functions?

I'm trying to find an algorithm on writing a high-level function - that doesn't have to halt - in Python (or Pseudo Code) that for a given list of functions [f1,...,fn] and a given list of inputs [x1,...,xn] prints fi(xj) (meaning all the pairs of functions and inputs) only once.

Of course the naive suggestion of implementing this would be:

for f in lst1:
   for x in lst2:
      f(x)

But the catch is that some of functions may loop forever on some inputs.

I am allowed to use a stepper (which has a step() method that makes one subsequent computation step of the function each time called)

I just need an idea or an algorithm on how to do so.

Upvotes: 1

Views: 177

Answers (1)

user395760
user395760

Reputation:

The general concept for this is dovetailing. Instead of trying to run each alternative to completion, you interleave the various alternative. For example, given three computations c1, c2, c3:

  • Run step 1 of c1
  • Run step 1 of c2
  • Run step 1 of c3
  • Run step 2 of c1
  • Run step 2 of c2, it terminates
  • Run step 2 of c3
  • Run step 3 of c1
  • Run step 3 of c3
  • ...

If a computation halts, this procedure reaches its halting state in finite time, regardless of how many other computations don't halt. Running k computations this way only slow each computation down by a factor of k. Since this is probably homework, I won't spell out how to apply this to your specific problem.

Of course, this does not halt if any of the computations doesn't halt. This is unavoidable (cf. halting problem) and not a problem since you'll finish with those that do halt (in your case: output their results) before you enter an futile infinite loop.

Upvotes: 7

Related Questions