What was the first turing-complete language? Know about the first machines and computers, but not the programming language.
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ Would you consider the (untyped) lambda calculus as a programming language? It is Turing complete, and was defined in 1936 -- the Turing machine is also from 1936. $\endgroup$– chiCommented Aug 25, 2017 at 18:54
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
9
Why not read this Wikipedia article.
The first programming languages designed to communicate instructions to a computer were written in the 1950s. An early high-level programming language to be designed for a computer was Plankalkül, developed by the Germans for Z1 by Konrad Zuse between 1943 and 1945. However, it was not implemented until 1998 and 2000.
Also, I think that it is wrong to consider a programming language as such to be Turing Complete since the concept of Turing completeness applies to a computational model, not to a programming language itself. For example, it is Turing machine, RAM machine, or Post systems that is Turing complete and not a set instructions or programming languages used to program them.
If our real life computers had infinite memory we could consider them a Turing machine equivalent to our abstract model we use in CS and Math, meaning that it is not programming languages or instructions sets used to program CPU that makes real life computers not equivalent to the abstract model.
answered Aug 25, 2017 at 17:55
-
$\begingroup$ Are these languages Turing-complete? Quote does not give info about that. $\endgroup$– rus9384Commented Aug 25, 2017 at 18:53
-
$\begingroup$ @rus9384 A programming language may be considered Turing Complete if it has a conditional jump and can read from/write to memory. All high-level programming languages are Turing Complete. These instructions are enough to simulate a Turing machine. $\endgroup$ Commented Aug 25, 2017 at 19:05
-
$\begingroup$ I've read in this thread: cs.stackexchange.com/questions/60965/… That C is not Turing-Complete, but from what I've read, Turig-Completeness is defined similarly as you also say. C can do this operations but doesn't have the infinite tape property, and I doubt any programming language lacks of this also. I believe/Think C is Turing-Complete, what do you say? . Thanks for the answer, I'm researching more on it. $\endgroup$– MSntsCommented Aug 25, 2017 at 20:09
-
1$\begingroup$ @fade2black The very first sentence of the Wikipedia link you give contradicts you. A programming language equipped with its operational semantics seems to be enough of a computational model for this purpose to me. Do you view Turing completeness as not applying to the lambda calculus? $\endgroup$ Commented Aug 25, 2017 at 21:04
-
2$\begingroup$ @PålGD There's a distinction between an implementation of a programming language on a particular computer architecture (which almost always operates in finite state, and hence is not Turing-complete), and the programming language as a mathematical construct. A programming language can be Turing-complete. A concrete implementation (a particular compiler or interpreter running on a particular system) is a finite approximation of the language. See my answer on the thread MSnts cited for a discussion of C. $\endgroup$ Commented Aug 25, 2017 at 21:16