A program can have finite output, yet still not halt. Example:

1: output "Yolo"
2: output ""
3: go to step 2

This only ever outputs "Yolo", despite never halting.

Is there some way, with a halting oracle, to determine whether a program will have infinite output or not?

Bonus: If not, what would be the Turing Degree of a machine capable of such a feat?


2 Answers 2


It's not clear what specific computational model you use. If you're using Turing Machines, then having a finite output is equivalent to having a finite number of distinct configurations (assuming that you're not allowed to "erase" the tape).

So we're considering the language of all TMs $M$ such that $M$ has a finite number of configurations when run on the empty input. Clearly this is Turing recognizable - simulate the machine and accept if it halts or repeats a configuration. Thus, the problem is in RE.

It's also very simple to show that it's not in coRE by a reduction from $A_{TM}$. So we conclude that the problem is in RE\coRE.

Now, given a halting-problem oracle, the problem is decidable: Given a TM $M$, modify it to a machine $M'$ such that $M'$ simulates $M$ and records the configurations, and if a configuration is repeated,or if $M$ halts, then $M'$ halts. Now simply run the oracle on $M'$.

  • $\begingroup$ What do you mean by "configurations"? And what's the difference between M' and M? $\endgroup$ Commented Mar 14, 2017 at 23:24
  • $\begingroup$ A "configuration" is a piece of information such that you know exactly how to continue the computation from it. For Turing machines, this comprises the state, the contents of the tape, and the location of the head. M and M' are just not the same machine, read the description carefully. $\endgroup$
    – Shaull
    Commented Mar 15, 2017 at 20:55



    while(i-th char ever appear) i++;


Parallelly foreach i in Positive Integer {
    Run the tested program, with "Will turing machine P halt?" written into "Will P halt in i steps?"
    print "lol"
} // Won't work if it tries to find a non-halting program from run-longer program list, which won't halt but halt for each i
  • $\begingroup$ Who is supposed to understand this answer? $\endgroup$
    – John L.
    Commented Dec 16, 2018 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.