patternMinor
With a halting oracle, can tell whether something will have finite output?
Viewed 0 times
canfinitewithhavehaltingoutputtellwilloraclewhether
Problem
A program can have finite output, yet still not halt. Example:
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?
1: output "Yolo"
2: output ""
3: go to step 2This 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'$.
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.