Mon, 13 May 2019 14:38:33 +0000

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]

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.