0
$\begingroup$

The definition of a computable function (according to Wikipedia) states "... a function is computable if its value can be obtained by an effective procedure. ... A procedure is formally called effective for a class of problems when it consists of a finite number of instructions."

Why is the restriction "finite number of instructions" necessary? Aren't the essential requirements computable in finite time and correct results? I can come up with programs that are infinitely long but terminate in finite time for any input, e.g., the function on the positive integers

// return 1 if x is odd, otherwise 0
if (x==1) {  return 1 }
else if (x==2) {  return 0 }
else if (x==3) {  return 1 }
...

Although this code is infinitely long that poses no problem as it can be generated on the fly until termination. One argument against this example could be that it has an equivalent finite counterpart.

However, given an infinite list of finite sized computer programs I can also define a function on the positive integers $i\in\mathbb{N}$ that returns the output of the $i$-th computer program for input $i$. Again, this algorithm terminates in finite time. Why is this function not considered computable.

(I'm interested in this questions in the context of Gödel's first incompleteness theorem, which also requires that the formal system is effectively axiomatized.)

$\endgroup$
5
  • $\begingroup$ Do you have a compiler that can handle infinitely-long generated-on-the-fly source code, though? $\endgroup$
    – Dan
    Commented Jul 15, 2022 at 19:31
  • 4
    $\begingroup$ You can't truly write an infinitely long program. What you can write is a description of such a program. And the description is finite. $\endgroup$
    – ZFCarla
    Commented Jul 15, 2022 at 20:01
  • $\begingroup$ "I can also define a function on the positive integers i∈N that returns the output of the i-th computer program for input i. Again, this algorithm terminates in finite time. Why is this function not considered computable?" Be careful here - what if the $i$th program never terminates? What function are you really defining, and what's your algorithm? You might be overlooking the actual halting-problem issues that lead to non-computability. $\endgroup$
    – Karl
    Commented Jul 15, 2022 at 20:09
  • $\begingroup$ @Dan I see no problem with a compiler as the unused code can be discarded and only finite space is required. $\endgroup$
    – Its_me
    Commented Jul 15, 2022 at 20:27
  • $\begingroup$ @Karl I consider a list of computable functions, where each one terminates. See 18:00 in youtube.com/watch?v=9JeIG_CsgvI $\endgroup$
    – Its_me
    Commented Jul 15, 2022 at 20:29

2 Answers 2

4
$\begingroup$

If your infinite list of instructions can be generated by a finite program, then whatever those instructions do can also be done by a finite program, so your function is still computable. It's only non-computable if it has no finite algorithmic description.

If we allowed infinitely long programs, then every function on $\Bbb N$ would be obviously computable (by an infinite sequence of cases, as in your "odd numbers" example), so "computable" wouldn't mean anything.

$\endgroup$
10
  • $\begingroup$ "computable wouldn't mean anything". It wouldn't mean a restriction, but I see no problem with that. Then, a computer languages would be universal for functions $\mathbb{N}\to\{0,1\}$. $\endgroup$
    – Its_me
    Commented Jul 15, 2022 at 20:35
  • $\begingroup$ "If your infinite list of instructions can be generated by a finite program, ... your function is still computable." Yes, but why not allow infinitely long code that cannot be generated by a finite program. I can conceive this e.g. as build by the list of all possible "conventional" computable functions (in e.g. Python). That's clearly well defined, although maybe not known due to the halting problem. $\endgroup$
    – Its_me
    Commented Jul 15, 2022 at 20:39
  • $\begingroup$ But why bother with a list of all finite programs if you can just list all the values of any function you want? $\endgroup$
    – Karl
    Commented Jul 15, 2022 at 20:56
  • $\begingroup$ You are right and a table is enough. But (it seems for me) an infinite table is fine and also the result computable in finite time. I currently don't grasp why any infinite table shouldn't make sense (so that we can define and compute with it) I'm tempted to search for meaningful ones. Isn't one build on the list of all conventional computable programs a candidate? Others state this list and claim it's perfectly well defined. Or is there a halting problem? $\endgroup$
    – Its_me
    Commented Jul 15, 2022 at 21:11
  • $\begingroup$ Such things are well defined but not always computable. E.g. you can write a (finite) program that takes an input $i$, generates the $i$th syntactically-valid program, runs it with input $i$, and returns the result. But this program doesn't compute a total function because it will run forever on certain inputs. If you instead define it so that you only consider terminating programs, then you successfully define a total function, but it isn't computable because there's no algorithm to generate the $i$th terminating program. $\endgroup$
    – Karl
    Commented Jul 15, 2022 at 21:19
3
$\begingroup$

With your model of computation, every subset $S \subset \mathbb N$ is recursive.

To prove this, denote the elements of $S$ in increasing order as $n_1 < n_2 < n_3 < ...$. Now build the following infinite machine. Start with a sequence of machines $M_1,M_2,M_3,...$ so that the only thing that the machine $M_i$ does is to print out $n_i$. Now build another machine which takes as input an element $k \in \mathbb N$, and then runs $M_1$, followed by $M_2$, followed $M_3$, and so on, reading the outputs, stopping at the first moment that there is output $n_i \ge k$ (assuming $S$ is infinite; an easy fix works when $S$ is finite). The machine then compares the final output $n_i$ to the input $k$, with the following result: if $n_i = k$ then $k \in S$, otherwise $k \not\in S$.

So your model of computation is not in accord with the Church/Turing thesis, in which there are in fact only countably many recursive subsets of $\mathbb N$.

$\endgroup$
3
  • $\begingroup$ So in a more 'laymen' language, OP's model of computation redefines computable functions, and hence recursive sets, and hence changes the amount of recursive sets, hence contradicting with the Church/Turing thesis? I'm not sure if I'm understanding this correctly. $\endgroup$
    – LGu
    Commented Jul 15, 2022 at 20:00
  • $\begingroup$ @LGu Yes, I want to extend "computable functions" and see what can be achieved by this. E,g, Gödels first incompleteness theorem doesn't apply anymore. I didn't look into the Church/Turing thesis (it's arguments), but I want to state that any proof build on Gödel is not valid, since Gödel assumes finite statements. $\endgroup$
    – Its_me
    Commented Jul 15, 2022 at 20:42
  • $\begingroup$ Yes, my model of computation is not a computable function and, thus, the Church/Turing thesis doesn't apply. Afaik (now) its called non-computable functions, hypercomputation or super-Turing computation. Thanks. $\endgroup$
    – Its_me
    Commented Jul 16, 2022 at 12:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .