Computable Functions

Question

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?

Answer 1

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

Answer 2

If $f:\Sigma^* \to \Sigma^*$ is function, and $\exists$ a Turing machine which on the input $w\in\Sigma^*$ writes $f(w)$, $\forall w\in\Sigma^*$, then we call $f$ as computable function. What is a computable function?

To generalize the above notion of computable function as much as possible anything that applies an algorithm to an input deriving an output is a computable function even when applied by the human being "computers" of the film: "Hidden Figures".

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.

The above function is computable for some inputs. Within the terms of the art of computer science a function is not computable unless it derives an output for all inputs in its domain.

The above function can be transformed into an instance of the halting problem, thus is construed as not computable in this case.