That can be hard, and can be impossible if the size of the input data is not bounded in advance. The obvious practical limitation is that you have to predict the memory requirements of your program before running it. In spite of that, FORTRAN was once the most widely used programming language. You had to figure out in advance how much memory your computation would need and allocate that. Let's look at a few examples of non-Turing complete languages that some people might nonetheless call programming languages.Įarly versions of FORTRAN did not have dynamic memory allocation. Require that the language supports arbitrary recursive functions Require that the language has arbitrary loops ( while) and dynamic memory allocation ( malloc) If you're designing a language, there are two major ways to ensure that the language will be Turing-complete: Now there are several very different kinds of Turing-incomplete languages out there, and they differ in what they can't do. So designing a Turing-incomplete language in which you can write all useful programs is still a very long-term research goal. the real question is, what useful program cannot be written in a Turing-incomplete language? Well, nobody has come up with a definition of “useful program” that includes all the programs someone somewhere has written for a useful purpose, and that doesn't include all Turing machine computations.
#COQ LANGUAGE SIMULATOR#
There is one thing you cannot do in any Turing-incomplete language: you can't write a Turing machine simulator (otherwise you could encode any computation on the simulated Turing machine). Conversely, a Turing-incomplete language is one in which there is some computation that cannot be expressed. So a Turing-complete language is one in which any computation can be expressed. First, I assume you've already heard of the Church-Turing thesis, which states that anything we call “computation” is something that can be done with a Turing machine (or any of the many other equivalent models).
0 kommentar(er)
