2
$\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
  • 3
    $\begingroup$ This is just the halting problem described in a slightly clumsy way. $\endgroup$ Commented Jan 12, 2021 at 7:10

2 Answers 2

1
$\begingroup$

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

$\endgroup$
-3
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ How does that answer the question? $\endgroup$
    – Nathaniel
    Commented Nov 15, 2021 at 18:26
  • $\begingroup$ @Nathaniel It much more directly answers the question now. $\endgroup$
    – polcott
    Commented Nov 15, 2021 at 18:35
  • $\begingroup$ Mixing ∃ and ∀ with English text doesn't really work IMO $\endgroup$ Commented Nov 15, 2021 at 19:30
  • $\begingroup$ @user253751 I am not mixing I am translating and generalizing. $\endgroup$
    – polcott
    Commented Nov 15, 2021 at 19:32
  • $\begingroup$ Is there a reason why a program cannot check if a string is a valid Python program? (Don’t know Python well enough, for a specific C implementation I would see no problem). $\endgroup$
    – gnasher729
    Commented Nov 16, 2021 at 17:57

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.