Return to the
comp.compilers page.
Search the
comp.compilers archives again.
| Related articles |
|---|
| From: | "Costello, Roger L." <costello@mitre.org> |
| Newsgroups: | comp.compilers |
| Date: | Mon, 13 May 2019 14:38:33 +0000 |
| Organization: | Compilers Central |
| Injection-Info: | gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="4687"; mail-complaints-to="abuse@iecc.com" |
| Keywords: | theory, comment |
| Posted-Date: | 13 May 2019 11:17:51 EDT |
| Content-Language: | en-US |
Hello compiler experts!
Possibly a philosophical question ...
As I understand it, a computer can understand (process) only a small set of
simple instructions such as addition, subtraction, comparison, branching, and
so forth. Everything we do daily on our computers is ultimately compiled down
to a (huge) number of these simple machine instructions.
In the last few years I have used some quite abstract languages such as the
constraint satisfaction language Alloy and the XML processing language XSLT.
It amazes me that these languages can be broken apart and compiled into the
small, simple set of instructions required by the computer.
This makes me wonder: Is a theoretical limit to the level of abstraction that
can be turned into machine instructions? Are there languages (abstractions)
that are so high level, so abstract, that they simply cannot be mapped to the
required set of addition, subtraction, comparison, branching instructions? Or
is there no limit to the languages/abstractions that can be compiled?
/Roger
[In 1936 Alan Turing proved a surprising theorem that a very simple
hypothetical computer, now known as a Turing machine, could calculate
anything that any more complex computer could, given enough time and
storage. Every computer built since the EDVAC in the 1940s has been
"Turing complete", able to compute what a Turing machine can, other
than that real computers have finite memories. So we can be pretty
sure that the simplicity of an instruction set doesn't limit what
a computer can do.
There are plenty of problems that are known to be undecidable. The
best known is the halting problem. You cannot write a program that
can inspect any arbitrary program and always tell you whether the
program it's inspecting will eventually halt or it will run forever.
Wikipedia has a lot on this topic. You can start here:
https://en.wikipedia.org/wiki/Turing_machine
-John]
Return to the
comp.compilers page.
Search the
comp.compilers archives again.