1
$\begingroup$

I'm learning about computable functions. Our definition for computable function is as follows:

Informally, a computable function is a function f : A → B such that there is a mechanical procedure for computing the result f(a) ∈ B for every a ∈ A.

they go on to give the following non-example:

A function that takes an input p (which I assume to be a program), and checks if p is a syntactically valid Python program without any user interaction that terminates and returns 1 if this is true, 0 otherwise.

I was just trying to understand why this is not computable. I know when I write a program with incorrect syntax that I get an error when I try to run it, so I am assuming that it is possible to check whether a program is syntactically correct, but I have a hunch that the terminating part has to do with the halting problem. Is this simply just an obscured halting problem?

$\endgroup$
1
  • 2
    $\begingroup$ This is just the halting problem described in a slightly clumsy way. $\endgroup$ – Yuval Filmus Jan 12 at 7:10
1
$\begingroup$

Yes, "that terminates" is the halting problem, not really in disguise but also not pointed out as problematic.

$\endgroup$

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.