2
$\begingroup$

Can a problem (described by a set of inputs and accepted answers) be designed such that for all programs which produce an answer in finite time for a (countably) infinite number of inputs, at least one of those outputs is incorrect.

That is, the program need not terminate for all outputs, but the outputs it does generate must all be correct, and there must be an infinite number of inputs for which it will terminate.

Not too sure about this, but my intuition says that the question may be related to the Halting problem/Turing machines.

As an example, the halting problem, (as far as I understand) does not meet this requirement, as one could run the input program, and output "terminated" if it terminates. If the input program never terminates, nor does the solution, so it never generates an incorrect output.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ This seems to ask, "are there undecidable problems", for which the answer is of course "yes". Duplicate? $\endgroup$
    – Raphael ♦
    May 19, 2016 at 21:06
  • $\begingroup$ When you say a set of inputs, do you mean a mathematical set? Can this set be infinite, or do you mean something else? $\endgroup$
    – jmite
    May 19, 2016 at 22:23
  • $\begingroup$ @jmite yes, I do. And it must be infinite, or it is impossible to terminate for an infinite number of inputs (as there aren't an infinite number to begin with) $\endgroup$
    – Daniel McIntosh
    May 19, 2016 at 23:54
  • $\begingroup$ @Raphael Will clarify the difference $\endgroup$
    – Daniel McIntosh
    May 19, 2016 at 23:55
  • $\begingroup$ @DanielMcIntosh In that case, Raphael is right, I don't see how this problem is different from "Do undecidable problems exist?" $\endgroup$
    – jmite
    May 19, 2016 at 23:57

2 Answers 2

Reset to default
3
$\begingroup$

A simplified example can be the following:

$$T( n ) = \begin{cases} \max \{ M(n) \mid |M| \leq n \} + 1 & \text{if such max exists}\\ 0 &\text{otherwise.} \end{cases}$$

In other words the "unprogrammable" (uncomputable) task $T$ (or better uncomputable function $T$) simply picks all programs $M$ of size at most $n$ as "input" and outputs the maximum value that they output on input $n$, plus 1.

Given a program $M_i$ that satisfies your assumption ( ... which produce an answer in finite time for a (countably) infinite number of inputs ...), there will always be an $x_0$ such that $|M_i| < x_0$ and $M_i$ on $x_0$ halts, and we have:

$$M_i(x_0) \leq \max \{ M(x_0) \mid |M| \leq x_0 \} < T(x_0)\,.$$

Improve this answer
$\endgroup$
0
$\begingroup$

The halting problem can be solution to your question.

You are saying that the algorithm for halting problem never terminates (or it terminates for a finite number of inputs) when the input is a "non-terminating" program. But this is not quite right. Because, you can actually devise an algorithm for halting problem that outputs "non-terminating" for some of the "non-terminating" inputs, but not all of them.

Let's say, I devise an algorithm that checks if the following code is reachable in the input program,

while (true):
   continue;
end-while

if it is reachable in an input program, the program has an infinite loop and does not terminate at all; otherwise, it may or may not terminate (I assume that this is a reachable part of program without loss of generality; there is an infinite number of programs with such reachable segment).

Therefore, there are an infinite number of "non-terminating" input programs, for which, my algorithm can actually find out that they are not going to terminate. But my algorithm is not able to find all input programs that are "non-terminating" (which means that the problem is still undecidable).

Improve this answer
$\endgroup$
2
  • $\begingroup$ First, detecting whether your given code is reachable is itself undecidable so your supposed algorithm doesn't exist. Second, you're not answering the question. Say that a Turing machine "kinda-decides" a set $S$ if every input it accepts is in $S$, every input it rejects is not in $S$ and it halts on infinitely many (but not necessarily all) inputs. The question asks if there's an infinite set that isn't kinda-decided by any Turing machine. The question already explains how the halting problem isn't the answer. $\endgroup$
    – David Richerby
    May 20, 2016 at 16:50
  • $\begingroup$ @DavidRicherby I did not say that the algorithm decides if that loop is reachable or not. I said it will check if it is reachable. There is an infinite number of programs that start with such loop and the program can easily detect them. Does this simple case explain it? $\endgroup$
    – orezvani
    May 22, 2016 at 1:51

Your Answer

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

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