3
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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'$.

$\endgroup$
  • $\begingroup$ What do you mean by "configurations"? And what's the difference between M' and M? $\endgroup$ – user2582622 Mar 14 '17 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 Mar 15 '17 at 20:55
0
$\begingroup$

2?

Turing2->Model:

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

Model->Turing2:

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
$\endgroup$
  • $\begingroup$ Who is supposed to understand this answer? $\endgroup$ – Apass.Jack Dec 16 '18 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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