-4
$\begingroup$

Must a partial halt decider be a pure function of its inputs?

A partial halt decider correctly decides the halt status of some of its inputs.

I am trying to write C code that would be acceptable to computer scientists in the field of the theory of computation.

In computer programming, a pure function is a function that has the following properties:

(1) The function return values are identical for identical arguments (no variation with local static variables, non-local variables, mutable reference arguments or input streams).

(2) The function application has no side effects (no mutation of local static variables, non-local variables, mutable reference arguments or input/output streams).

https://en.wikipedia.org/wiki/Pure_function#Compiler_optimizations

I created a partial halt decider that is able to tell when it is called in infinitely nested simulation. It can only do this if it has a static memory variable to keep track of the simulation of its input across recursive invocations.

Does this still meet the Halting Problem requirement that the function must be a pure function of its inputs?

$\endgroup$
32
  • 1
    $\begingroup$ I wonder if some context is missing here. Require pure functions where and according to what? An actual complex language like C is hard to formalize, but what are you trying to accomplish? $\endgroup$
    – Juho
    Commented Sep 18, 2021 at 6:17
  • $\begingroup$ Randomized functions do not necessarily return identical values for identical inputs. Implementations of operations on data structures do have side effects on the data structure. Perhaps you should narrow down "theory of computation" when making this kind of statements. $\endgroup$ Commented Sep 18, 2021 at 8:10
  • 4
    $\begingroup$ You should delete the part of this question where you have claimed to solve the halting problem. You have not solved the halting problem, and your repeated attempts to "prove" that you have solved the problem merely attract downvotes. You can simply ask whether a partial halt decider must be pure. You should also define what a partial halt decider is. Many programs can be said to correctly decides the halt status of some of their inputs. In fact I think the only ones that don't are the ones where programs can't be inputs, and the ones where no values are output. $\endgroup$ Commented Sep 19, 2021 at 21:16
  • 1
    $\begingroup$ Please limit your post to one question only. Also, it is unclear to me how your code-snippet is relevant. Note that in general, we advise against writing (pseudo)code in favor of clear but precise descriptions of the algorithm. ... Reading between the lines a bit, I suspect you may be falling in the "trap" of confusing precision with formalism. Arguments made in notation are often precise, but can obscure the situation if the notation is not designed to answer this type of question. So, when in doubt, retreating to precise, English, descriptions of your object can help understanding it. $\endgroup$
    – Discrete lizard
    Commented Sep 20, 2021 at 5:15
  • 2
    $\begingroup$ @polcott You haven't defined "partial halt decider" in sufficient detail for that question to be answerable. Is it a mathematical function? A C program? A Turing machine? By default the answer for a C program is "no" because C has global variables, for a mathematical function is "yes" because all mathematical functions are pure, and for a Turing machine is "mu" because the concept of a pure Turing machine has not been defined. $\endgroup$ Commented Sep 20, 2021 at 9:12

1 Answer 1

3
$\begingroup$

A decision algorithm is required to behave as an "observationally pure" function. In other words, its externally observable behavior (for someone who can run it on inputs of their choosing and observe what it outputs) must be consistent with it being a pure function.

Presumably, unless you specify otherwise, any normal reader of your definition of "partial halt decider" would assume that such an algorithm is also required to be observationally pure.

Why? Because the algorithm is supposed to compute a mathematical function, and a mathematical function is pure, so any algorithm that correctly computes it also must be observationally pure.

There is no requirement that the particular implementation of the algorithm be pure in the sense you have listed. It is OK to have code that, for instance, defines a local variable and then overwrites its value. For instance, a Turing machine can overwrite what is written on the tape. Nonetheless, from the perspective of any external observer who only sees the input-output behavior of the Turing machine, it remains observationally pure.

$\endgroup$
10
  • $\begingroup$ This is the kind of thing that I was expecting and it is very helpful. I will paraphrase what you said to test my understanding. As long as there is one set of inputs such as such as the formal parameters to a function and a single output such as return value of {1,0} (indicating true or false) from this function, then whatever occurs in-between does not make any difference. $\endgroup$
    – polcott
    Commented Sep 19, 2021 at 3:41
  • $\begingroup$ It looks like you may be reiterating the first requirement listed above and saying that we can ignore the second requirement: (Is this correct?) (1) The function return values are identical for identical arguments (no variation with local static variables, non-local variables, mutable reference arguments or input streams). $\endgroup$
    – polcott
    Commented Sep 19, 2021 at 15:37
  • $\begingroup$ @polcott That is what D.W. is saying. $\endgroup$ Commented Sep 21, 2021 at 20:01
  • $\begingroup$ @user253751 so then it is OK to use a pair of static memory variables to keep track of the execution trace of P across recursive simulations of P/H as long as the initial input always derives the same final output. $\endgroup$
    – polcott
    Commented Sep 21, 2021 at 20:56
  • 1
    $\begingroup$ @polcott Note that if your algorithm was "observationally pure", you could write an equivalent version without any global or static variables. In particular, the "observationally pure" requirement requires that your algorithm returns the correct answer even if all the global/static variables have their default values when the algorithm begins. $\endgroup$ Commented Sep 22, 2021 at 8:02

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.