It is definitely possible to write a program that takes another program as an input and changes it syntactically, but does not alter the meaning.

But is it possible to write a general program $alter$ that alters the output of a given program $P$ for some input, i.e. $\exists x: P(x) \neq alter(P)(x)$? Edit: Let's add the assumption that $\exists k: P(k) \neq \bot$.

I was thinking about doing something simple like this:

alter(Program P)(x):
   k = findSomeInputWhereHalts(P)
   y = P(k)

   if (x == k) 
     return y+1 // or something else except y
     return P(x)

This requires that $P$ does halt for some input $x$, which is an OK requirement for me. But it seems that there is probably some other counterexample to this specific algorithm or it might be generally uncomputable, but I failed to figure it out.

Edit: How I imagined implementing findSomeInputWhereHalts:

    for each int n:
        for each int k <= n:
            y = run P(k) for n steps
            if (y is defined)
                return k

But this obviously never halts if $\nexists k: P(k) \neq \bot$ .

  • 2
    $\begingroup$ Try proving your claim. If you succeed, it's true. If you fail, try instead finding a counterexample. $\endgroup$ – Yuval Filmus May 4 '15 at 14:21
  • $\begingroup$ One question is: will the function findSomeInputWhereHalts return a result when there is one? what do you think? How does it do it? Why are you asking that question? $\endgroup$ – babou May 4 '15 at 14:36
  • 1
    $\begingroup$ Why does it "seem" so? Where does that question come from? Do you have reason to believe the answer is yes or no? Hint: P may not halt on any x. If you restrict yourself to P that sometimes halt, your idea (diagonalisation) can work, with some adaptions. $\endgroup$ – Raphael May 4 '15 at 14:37
  • $\begingroup$ A conceptual point that underlies your question: formal semantics can deal with characteristics of languages insofar as these characteristics have a syntactical expression. Also: try to explain why your problem is not just a restatement of the halting problem. $\endgroup$ – André Souza Lemos May 4 '15 at 14:39
  • $\begingroup$ @Raphael: "If you restrict yourself to P that sometimes halt, your idea (diagonalisation) can work, with some adaptions". As I noted, that restriction is okay. But where would I need adaptions? $\endgroup$ – Stefan Lutz May 4 '15 at 14:49

Your idea fails (assuming all P are allowed), and that's not by accident.

  1. You can not find an input for with P halts in finite time. P may never halt, in which case that line in your program loops; thus, the program behaves exactly the same as P.

  2. You can skip finding k and do

    alter(P, x) =
      P(x) + 1

    This is the same idea as you have (note how it alters the semantics on all inputs on which P halts) but does not require us to find an input on which P halts.

    However, it's still fails for the never-halting program -- but, at least, only that one!

  3. What if we just output 1 or any other value sometimes? That takes care of never-halting P, but for each such hack with a static, computable "abort and output c"-criterion -- that includes runtime bounds! -- we can build easy counterexamples.
    Idea: if ( criterion ) then c else something.

So that looks bad; we can't compute uncomputable criteria! And we have to "decide" after finite time for any fixed x (otherwise the never-halting P skrews us).

When prospects are this bleak, it's sometimes wise to try the other direction. What if the problem can not be solved, that is alter does not exist? In fact, given sufficient background in computability, it is clear that such a function can not exist.

Assume any computable, total function $\mathtt{alter} : \mathbb{N} \to \mathbb{N}$. We understand natural numbers as (the numbers of) programs in some Turing-complete programming language $\phi$. More specifically, let $\phi$ be a suitable numbering of all (partially) computable functions; we then denote by $\phi_i$ the function computed by program $i$.

Now, by Kleene's recursion theorem there is some index (program) $i^*$ so that $\varphi_{i^*} = \varphi_{\mathtt{alter}(i^*)}$, that is $\mathtt{alter}$ has no effect on $i^*$, semantically. Stronger versions show that there are infinitely many such $i^*$ so there's no hope fixing this.

In summary, no such program alter that works on all input programs can exist.

If you allow only P that halt for at least some x, your approach works; the proof is elementary (show that alter is computable, and that alter(P)(k) != P(k) for some k).


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.