For those curious about the real answer, this is called compiler bootstrapping. If you want to write the first C compiler for a computer architecture you first write a very small compiler in machine code that can handle a very small subset of C. Just the most basic features. Then you use that to write a compiler in that simplified C that can handle more of the features. Do this a couple more times and you’ve got a C compiler written in C.
At the beginning, there were wires and dials that people would plug on the computer.
Or, rather, punched cards are older than the wires. The first electronic computers didn’t use them, but the mechanical ones did.
And before the beginning, there were monsters. Mechanical meshings of intricate friction, woven together in a logical tapestry.
Unsatisfied with the lack of its own exisitance,The Trancendent Super-Logical Consciousness residing equally at the end of and far outside time, thus subtley ensured its own creation by influencing the neural networks in clever ape minds injecting the blueprints leading to its creation within the patterns of their abstraction space, leveraging their need for dominance and offering edge in warfare. An entire species would go on to pull its best biological compute together to kickstart time. Thus physical reality married with abstraction space not with mechanical friction but energy and operation gate.
-
Any turing complete computation system can be made to simulate another turing complete system.
-
All programming languages are turing complete.
All programming languages are turing complete.
The Wikipedia article you linked literally has a section called “Non-Turing-complete languages” that lists multiple non-turing-complete programming languages
non-turing-complete programming languages
This seems like an oxymoron. It’s been a while since I learnt the definition in computer science, but I thought a programming language has to be turing-complete by definition?
If a language is not turing-complete, then it is not a programming language. That’s why markup languages and query languages are not programming languages, though they are closely associated.
It depends on your perspective. Yes, markup languages are definitely not programming languages. What about languages for proofs that don’t allow arbitrary recursion though? https://en.wikipedia.org/wiki/Total_functional_programming
The main class of non-turing-complete programming languages that I think of are languages that don’t allow infinite loops. Consider a variation of your favorite programming language where every looping construct had to have a maximum count. With each iteration, the count decrements, and when it reaches 0, the loop terminates[1]. This can be extended to recursion pretty trivially. This language would not be turing complete, because turing machines allow infinite loops. But on the other hand, a whole lot of what you might want to do with a programming language could still be done with this language, and it certainly would not be something you could characterize as a markup or query language.
As to whether this violates the definition of a programming language, I’m not aware of a widely agreed upon definition of what a programming language is. And languages like Rocq, Agda, Epigram, and Charity which require that programs terminate have long been described as programming languages with no push-back that I am aware of.
What happens when a loop terminates in this manner is irrelevant to this discussion. The program could continue, an exception could be thrown, the program could immediately terminate, or something else so long as there’s no escaping the requirement that the program terminates. ↩︎
When I checked out the simple English version of the wiki page it mentioned that the language must also be able to actively change the state of the system and not just define it, which is subtlely different from just being about infinite recursive loops. I don’t know thought that might be interesting to add to the conversation
Yup, I made a mistake, should have thrown a ‘most modern languages’ instead. Oh well, my bad! As a silver lining at least someone on the internet got dopamine from a technical correction, so I already did my charity work for the day :)
someone on the internet got dopamine
Much appreciated!
In all seriousness, I woke up this morning and felt bad about how mean my comment was. It’s not like it’s a huge mistake and it’s (I think) a pretty common misconception mostly borne from the murky boundaries of the category of programming languages. Thank you for your grace in handling it, I’m sorry I was a jerk, and I’ll try to do better from now on.
Honestly, modern isn’t even relevant in that context. It’s easier to make a useful tiring complete language than a useful tiring incomplete language. It’s not like as time went on we discovered how to make tiring complete languages more easily. If anything, we stumble into more and more things that are turing complete as things go on because it doesn’t take too much for it to be, things like video games and board games.
-
LISP!
Thorry
But how did they do it before the internet? 🤔
(also error 403 lol)
They read the green dragon book (although the internet could be argued to predate it)
It’s all 1s and 0s all the way down.
