Can we meaningfully state for what proportion of possible programmes we can determine if they halt, do not halt, or wether it is still undetermined?

[My apologies, I am not a computer scientist, merely an interested amateur. I apologise if this question does not make sense, is a known result, or a duplicate]

To quote Wikipedia:

The halting problem is the problem of determining, from a description
of an arbitrary computer program and an input, whether the program
will finish running, or continue to run forever.

This cannot be solved in general for all possible program-input pairs.

However, for a subset of programs/inputs we can determine by inspection, or simply running them, whether they will halt - e.g. I believe that a program with no looping or recursion will always halt, and a program with an impossible loop-ending condition will never halt.

One could imagine a program which when taking a program/input runs it for a length of time and reports 'halts' if it halts in that time, 'doesn't halt' if it has entered an infinite loop in that time, or 'undetermined' if neither has happened yet.

If we ran the program for increasing lengths of time, we must expect the proportion of programmes for which 'undetermined' is returned to reduce - i.e. 10% of programs may halt or enter an infinite loop when run for 1 hour, but 20% when run for 10 hours.

Can we, and do we know what the expected outputs of such a machine might be given a sufficient time? i.e. do 'almost all', 'most', 'some' or 'almost no' programs halt? Do 'more' programs enter an infinite loop than halt?

And if we cannot answer this question in general, can we answer it for a Turing machine with a limited number of states? e.g. do most 4-state Turing machines halt?

There are infinitely many Turing machines, so the notion of 'most' is a bit tricky to define. But with a reasonable interpretation, the answer will depend on the programming language. So, the question cannot be answered in general terms.

To get some flavor for why this might be: consider an assembly language that has 10000 opcodes, where 9000 of them are "halt" instructions that when executed cause the program immediately to halt, 999 of them are arithmetic instructions (that don't trigger any control flow), and 1 is a conditional branch. Then in some sense, most programs halt, because a random program is likely to contain one of the halt instructions before its first branch instruction. Conversely, consider an assembly language that has 10000 opcodes, where 9000 of these are instructions that immediately enter an infinite loop, 998 are arithmetic instructions, one is a halt instruction, and one is a conditional branch. Then most programs don't halt, because most contain one of the infinite-loop instructions before the first halt or conditional branch.

This proportion is closely related to Chaitin's constant. The value of Chaitin's constant cannot be computed by any algorithm.

Finally, the question as you have posed it is in some sense not well-defined. "Halting" is a property of a program and an input. It doesn't make sense to ask whether a program halts, or calculate the proportion of programs that halt. So, we can't ask what proportion of 4-state Turing machines halt. We could ask what proportion of 4-state Turing machines halt on all inputs. This is tricky, though; given a Turing machine, checking whether it halts on all inputs is not computable.

StackExchange Computer Science Q#149889, answer score: 5