ccomputation-theoryformal-verificationformal-methodscomputability

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


The characteristics of a computable problem are:

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".


Solution

  • 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:

    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.