patternMinor
Official Name for the “First” Programming Language Developed by Turing?
Viewed 0 times
thedevelopedprogramminglanguagefirstnameforturingofficial
Problem
As is widely known, Alan Turing discovered/invented the Turing Machine in his classic 1936 paper. Here he also gave how these machines are specified in terms of their machine states and instructions on how they operate. Is there any official or widely accepted name for this "first" mathematically defined programming language$^*$ $L$ that consists of a specification of a Turing Machine together with its transition function? Clearly by definition this language is Turing complete and hence can simulate any other algorithmic programming language. For instance here would be how program of $L$:
//Some specification of the machine $M$'s states, initial state, final state, allowable tape symbols, blank tape symbol, etc.
// If $M$ is in state 0 and sees a 0, then write 1, move right, and enter state 2
// If $M$ is in state 2, sees a 0, then write 0, move right, and enter state 3
// etc
*By first mathematically defined programming language, I'm ignoring for the moment innovations like automated loom printing or natural programming languages like DNA/RNA which are definitely algorithmic, and instead focusing on a particular strand of algorithmic specification that most closely matches what is commonly thought of as a programming language today. There are also other mathematically defined systems that were shown to be Turing equivalent around the same time as Turing, but none of these really caught on in terms of influence as Turing machines and their programming language did.
//Some specification of the machine $M$'s states, initial state, final state, allowable tape symbols, blank tape symbol, etc.
// If $M$ is in state 0 and sees a 0, then write 1, move right, and enter state 2
// If $M$ is in state 2, sees a 0, then write 0, move right, and enter state 3
// etc
*By first mathematically defined programming language, I'm ignoring for the moment innovations like automated loom printing or natural programming languages like DNA/RNA which are definitely algorithmic, and instead focusing on a particular strand of algorithmic specification that most closely matches what is commonly thought of as a programming language today. There are also other mathematically defined systems that were shown to be Turing equivalent around the same time as Turing, but none of these really caught on in terms of influence as Turing machines and their programming language did.
Solution
Turing machines are not programmable. Each Turing machine computes only one function. Hence they do not use any
programming language. What you see as a language is the description of
the machine itself, not of a program in some programming language. Thus the name "Turing machine" is the only appropriate terminology.
Now it turns out that there are devices that can emulate Turing
machines, such as a computer programmed to do such an emulation. They
can use the description of a Turing machine to simulate its
computation. This is very similar to a hardware emulator that can
mimic the hardware of a computer from a formal description of the
circuits.
The abstract theoretical model of such an emulation, as then performed
by a Turing machine is called a Universal Turing machine. But
universal Turing machines are in no way specialized for that kind of
description. It is a much more general concept. The most general name for the input to a universal Turing machine could possibly be "Natural numbers".
However, in his 1936 paper On Computable Numbers, with an Application to the Entscheidungsproblem, Turing uses the kind of encoding you have in mind as input to be properly encoded for his universal computing machine.
He calls it "standard description", abbreviated as "S.D.".
But it is not the first Turing complete language, even ignoring earlier theoretical work such as done by people like Church and Gödel.
You view of history is missing an earlier invention, which is Charles Babbage's Analytical Engine. Lady Augusta Ada King, Countess of Lovelace, is considered the first programmer in history, though her computer, Babbage's engine, never worked in her lifetime. I do not know that the "assembly language" for the engine received a name. According to Wikipedia it would have been Turing complete.
programming language. What you see as a language is the description of
the machine itself, not of a program in some programming language. Thus the name "Turing machine" is the only appropriate terminology.
Now it turns out that there are devices that can emulate Turing
machines, such as a computer programmed to do such an emulation. They
can use the description of a Turing machine to simulate its
computation. This is very similar to a hardware emulator that can
mimic the hardware of a computer from a formal description of the
circuits.
The abstract theoretical model of such an emulation, as then performed
by a Turing machine is called a Universal Turing machine. But
universal Turing machines are in no way specialized for that kind of
description. It is a much more general concept. The most general name for the input to a universal Turing machine could possibly be "Natural numbers".
However, in his 1936 paper On Computable Numbers, with an Application to the Entscheidungsproblem, Turing uses the kind of encoding you have in mind as input to be properly encoded for his universal computing machine.
He calls it "standard description", abbreviated as "S.D.".
But it is not the first Turing complete language, even ignoring earlier theoretical work such as done by people like Church and Gödel.
You view of history is missing an earlier invention, which is Charles Babbage's Analytical Engine. Lady Augusta Ada King, Countess of Lovelace, is considered the first programmer in history, though her computer, Babbage's engine, never worked in her lifetime. I do not know that the "assembly language" for the engine received a name. According to Wikipedia it would have been Turing complete.
Context
StackExchange Computer Science Q#44316, answer score: 8
Revisions (0)
No revisions yet.