How do you prove whether a simple unmeaningful code is computable or not?

Question

The characteristics of a computable problem are:

• Complete means that it covers all the cases;
• Mechanistic means that it is precise;
• Deterministic means that the same output will be provided if the same input is entered.

Correct me if I'm wrong, I found that through researches and don't fully knew what it actually means except for deterministic.

So, I'm trying to prove a simple code such as:

int i = 0;
do{
    int j = 0;
    do{
        printf("Hello\n");
        j++;
    }while (j < n);
    printf("Hello\n");
    i++;
}while (i < n);

is computable.

I know how to show like it's deterministic since it's fairly obvious but I am not sure how to show that it's mechanistic or complete.

The Complete characteristic, from what I understand it's more of a "Is there any way that the code fail to be executed or returned as error?" such as opening a text file there's a chance that file doesn't exist because wrong file name entered or wrong location entered, etc.

But In the case of the snippet code above, how should I prove that it's complete?

As for the Mechanistic "whether 1 + 1 = 2 instead of 3?".

Same thing, for the case of snippet code above, how can I prove that it's precise since the code itself doesn't solve any problem it's just printing "hello" according to the n values? Which in this case n^2 + n number of "hello".

Answer 1

You are mixing up a few things.

Firstly, you provided a piece of code and asked how to prove that it is computable. But that doesn't make any sense - a piece of code cannot be computable or not computable.

A (mathematical) set can be computable or not computable. And based on that, everything else that is also a set: for example a language (which is a set of strings), a decision problem (which is a set of accepted inputs) or a function (which is a set of key-value pairs).

Secondly, the "characteristics" you mention don't define computable problems. I don't know where you got them from, but they are at best a very informal description of some aspects of an algorithm for solving a computable problem. So I think you are not talking about computable problems, but about algorithms. But given that your characteristics are informal, you can't prove them.

So here are some slightly more precise (but still not formal) statements that may be helpful:

• A problem is computable iff there exists an algorithm that solves it.
• An algorithm solves a problem iff
  • it can be expressed within a standard model of computation (e.g. a Turing Machine or a standard programming language);
  • it is sound with respect to the problem: any answer produced by the algorithm belongs to the answer set of the problem;
  • it is complete with respect to the problem: any element of the answer set of the problem is produced by the algorithm;
  • the algorithm halts on all inputs.

Now these are characteristics that are precise enough that you can actually use them for proving that a problem is computable, or that an algorithm solves a particular problem.