0
$\begingroup$

By an algorithm $A(p, t)$ attempting to decide whether the program $p$ halts or not by running the program for $t$ seconds (the timeout) and trying to prove that it doesn't halt at the same time, can it decide more and more programs as the time gets bigger, so that any program would result in the algorithm in showing us "halts" or "doesn't halt" in some time as it really does? More precisely, by $H(t)$ representing the number of the programs being decided ($H(t) = |\{p \in Programs: HALT(A(p, t))\}|)$:

$\forall n \in N: \exists t > 0: H(t) > n$

and

$\forall p \in Programs: \exists t > 0: HALT(A(p, t))$

Does such an algorithm $A$ exist?

$\endgroup$
3
  • $\begingroup$ Why you have an additional $HALT$ before your centrally concerned algo decider $A(p,t)$? Do you mean your $H(t)$ only contains counts of those decided/decidable to be only halted? While you described in natural language you want to count both halted and unhalted. And not sure what's your intended difference from your 2nd formulation with the classic Halting problem. $\endgroup$
    – cinch
    Jul 31, 2023 at 20:11
  • $\begingroup$ @mohottnad The program can surely handle the ones that halt. For any program that halts, would exist a time no matter how big it is, where the program would halt in that time. I just wrote $HALT(A(p, t))$ as a representation of: "the program $A$ decides and in its result halts, whether $p$ halts or not, in $t$ seconds" $\endgroup$
    – sbh
    Aug 3, 2023 at 11:36
  • $\begingroup$ Then your idiosyncratic double predicates above is essentially intended to express a Type-0 semi-decidable language grammar in Chomsky hierarchy, still not decidable even such an algo $A$ exists by some clever timing checks in its loop. Some proofs of the classic Halting problem just follow this automata/language type route. $\endgroup$
    – cinch
    Aug 4, 2023 at 18:32

3 Answers 3

0
$\begingroup$

By your definition such an algorithm does not exist.

In fact, the algorithm should give an answer in finite time. At whatever timestamp $t>0$ the algorithm $A$ stops, there always exists a program $p$ which halts after $T>t$ time, so that $A$ can not detect if $p$ halts or not.

The problem is that $A$, being al algorithm, can run for finite time, while the set $\{t \in \mathbb{R} \ : \ \exists \ p \in P \ : \ p \text{ halts after } t \text{ seconds} \}$ is superiorly unbounded.

Since I'm not sure on what you asked I provide also another answer:

If the program $p$ is fixed, either it halts at time $t$ or it does not halt. But also in this case, we can not know if it halts or not without knowing $t$ and this is the classic alting problem. You can find it on Wikipedia or on various books

$\endgroup$
0
$\begingroup$

Programs are enumerable, so you can organize rounds where you execute one elementary step of every program in turn and in the end add a new program.

The more time you spend, the more halting programs you will find.

$\endgroup$
1
  • $\begingroup$ Yeah, that is the first expression being expressed. What about the second one? It can be directly implied by the first one, right? $\endgroup$
    – sbh
    Jul 30, 2023 at 16:01
0
$\begingroup$

You can write a program that detects that some programs halt with some inputs, and that some programs won't halt with some inputs (just not for all programs and all inputs).

I'm sure there are programs where you can prove "with input X, it will either halt within s seconds, or it will not halt at all". And then of course you can decide whether the program halts with input X by running it for s seconds. Take testing a number n for primality by dividing it by all integers other than 1 and n (so it halts when you find a non-trivial divisor, and if n is prime it never halts). That program will either halt within $\sqrt n$ steps or it will not halt at all.

And of course you can simulate any program with any input, and if that program with that input halts, then your simulation will detect that eventually. If you simulated all programs with all inputs, then you would be able to enumerate all halting program/input pairs. The problem is that after any finite amount of time, you don't know whether and which of the other problems will halt and which will not.

$\endgroup$

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.