HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

With a halting oracle, can tell whether something will have finite output?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
canfinitewithhavehaltingoutputtellwilloraclewhether

Problem

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?

Solution

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

Context

StackExchange Computer Science Q#52202, answer score: 3

Revisions (0)

No revisions yet.