Arbitrary Programs that Halt

Question

I've been learning about Theory of Computation lately, and i'm trying to link general programming with the Theory of Computation. I thought of considering any arbitrary program that halts, as an algorithm for solving some specific computational problem in the sense of Theory of Computation.

For some programs (like a calculator program, etc.), it is really easy to see them as an algorithm for solving some computational problems.

It seems to me, however, that some other programs are really not solving any computational problem.

Computational problems have instances, which can be see as the possible inputs to the algorithm that solves the problem (if the problem is computable), and for each instance there is an answer, which can be seen as the outputs to the algorithm.

But now, how could a Hello World program (prints the string "Hello World") be considered as the algorithm for solving some computational problem? What would be the computational problem, and its possible instances?

Other examples would be a program that solely does the job of establishing a connection to another computer over a network, and then proceeds to send messages to it, closing the connection in the end.

Is it really an algorithm to solve some computational problem?

So I'm thinking that programs (even considered the subset of those that halt) don't ALWAYS relate to Theory of Computation. In another words, there are some programs (mostly the ones that seems fixed procedures with no inputs) that don't represent the algorithm/solution for a problem, and hence can't be represented in a true Model of Computation like a Turing Machine.

Any opinions on the relation between programs that halt in general and Computation Theory?

Answer 1

There are many issues in your question. I am no longer very expert in some of them, but let's try.

Basically, a standard program as you like it takes some input $I$, satisfying some property $P$, and does things with it so as to obtain an output $O$ satisfying some property $Q$ involving $I$ and $O$: $Q(I,O)$.

This program solves a problem corresponding to a constructive proof that $\forall I, P(I) \implies \exists O, Q(I,O)$. The problem is to find $O$ when given $I$. This may actually be read as a specification of the problem, of the program.

It is easy to apply this to a sorting program, for example.

This works nicely in functional programming.

But when you quit functional programming, things become harder to explain.

Typically, printing a string is a side effect, hence not functional.

If instead of printing you were considering just producing the string "Hello world", for whatever purpose, the you would have a functional program meeting a degenerate case of the above schema, because there is no input.

The problem reduces to: produce the string "Hello world" and corresponds to the specification $\exists O, O=\text{"Hello world"}$. The lack of input makes the universal quantifier unneeded.

But printing is something else, as is network reconfiguration. They are not directly functional operations.

Now, it is possible to simulate non-functional structures in a functional context by building appropriate domains of computation. But this often makes things a lot more complex. And the understanding I tried to give is no longer so obvious.

Dealing with these issues has been one of the main purposes of denotational semantics. Much of the research in language design is about bridging the gap between functional understanding and the requirements of non functional practices.