4
$\begingroup$

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.

<0, 0, 1, R, 2> // If $M$ is in state 0 and sees a 0, then write 1, move right, and enter state 2

<2, 0, 0, R, 3> // If $M$ is in state 2, sees a 0, then write 0, move right, and enter state 3

<2, 1, 0, L, 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.

Improve this question
$\endgroup$
7
  • $\begingroup$ Cross-posted from stack exchange. Feel free to delete this question if it's better suited there. $\endgroup$
    – lesnikow
    Jul 10, 2015 at 21:18
  • 1
    $\begingroup$ No, there is no official name, and I also wouldn't call this a programming language. The relevant official term is "Turing machine". $\endgroup$
    – Yuval Filmus
    Jul 10, 2015 at 22:05
  • 1
    $\begingroup$ DNA/RNA may be algorithmic, but I have been wondering for a long time whether all its interpreters agree on the semantics, the computed function. $\endgroup$
    – babou
    Jul 10, 2015 at 22:54
  • 1
    $\begingroup$ For future reference, please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. $\endgroup$
    – D.W. ♦
    Jul 11, 2015 at 2:15
  • $\begingroup$ @D.W. It was ambiguous which was the appropriate site. If one of those seems inappropriate, apologies, and feel free to delete it. $\endgroup$
    – lesnikow
    Jul 11, 2015 at 3:30

1 Answer 1

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Sorry I should have been more specific. The machine is a Universal Turing Machine and the program is (an encoding of) the set of five-tuples that describe what Turing machine is being emulated. $\endgroup$
    – lesnikow
    Jul 10, 2015 at 22:47
  • 1
    $\begingroup$ The language of inputs to a universal Turing machine does have a name (probably several). I Guess the most common one is Natual numbers. However, in his 1936 paper, Turing uses the expression "standard description" (S.D.) for the input given to his universal computing machine. $\endgroup$
    – babou
    Jul 10, 2015 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.