1
$\begingroup$

What was the first turing-complete language? Know about the first machines and computers, but not the programming language.

$\endgroup$
  • 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$ – chi Aug 25 '17 at 18:54
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are these languages Turing-complete? Quote does not give info about that. $\endgroup$ – rus9384 Aug 25 '17 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$ – fade2black Aug 25 '17 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$ – MSnts Aug 25 '17 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$ – Derek Elkins Aug 25 '17 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$ – Gilles 'SO- stop being evil' Aug 25 '17 at 21:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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