Programming as a language

Everyone must be acquainted with the term in English jargon programming language. Any language is a tool to communicate most probably within the biological species which makes the species naturally selected in evolution. There were many attempts to formalize mathematically a machine to make it say a species to effectively communicate with humans and vice versa. That led to the computerized digital world we live in. The most basic definition is Finite State Automata(FSA) which has a start state, set of symbols to navigate between other states and an end state of accepting member statement of the language. FSA is known to express regular language(heirarchy of languages by Chomsky: leave it for another article). FSA with conceptual stack is known to express context free languages. FSA with linear bounded Turing machine is known to express context sensitive languages. When trying to realize the theoretical framework with real program we get to know the basics that stick well in mind. See the following program in C,

In the above simple program if you think deeply how the computer runs this program to give us the output 30, you are in awe. This program is taken as input by another program that is compiler and then converting into binary, this program executes to print 30. If thinking still more how Chomsky hierarchical play works here, the basic FSA is used for identifier "i,j" matching the rules of variables naming, like not exactly keywords, not number in the beginning, no space in between. Also FSA takes care of numerical constants, string constants, character constants not to be messed up in syntax. Next comes FSA+Stack which actually handles most of the balanced parentheses "{},(),[]", in our case it is simply limited to the main function. Next in line is the FSA+Linear bounded TM, which is the compiler which has the power to correct all syntactical error. Without clearing the compiler check statistically typed language like C can never move to execution.

But thinking of compiler one cannot ignore Turing machine and the Halting problem. A Turing machine which when kept conceptually as a machine even with infinite memory cannot distinguish if it will halt for a particular input or not, unless by running over the problem itself. Consider the following function,

In the above function halts() is assumed to be a total function that returns True given a program as input that always halt and otherwise. But the above snippet, when the halts(g) is True g() loops forever and when halts(g) is False g() returns. This is in direct contradiction to the assumption leading there can be no total function halt() that can predict if a program can halt or not by itself. So compiler too never checks over its bound like looping forever code. It checks all the syntactic errors and unbalanced parentheses and leaves the complete logic to the programmer. It is a kind of grammar teacher who guides early budding human programmer. With chatGPT in play we are even wondering has AI passed Turing test.