> On Dec 13, 2017, at 3:04 PM, Paul Gilmartin > <[email protected]> wrote: > > On 2017-12-13, at 12:13:54, Seymour J Metz wrote: > >> Script is Turing complete, so in a pinch you can do things that you don't >> normally think of as document processing, e.g., generating backup schedules. >> I much prefer a good markup language to a WYSIAYG word processor. Take m$ >> office - please! >> > One collateral consequence of a Turing-complete language is that it's > impossible to define its syntax formally. > > -- gil >
It is? A Turing machine is simply a finite-state-automata with a fixed number of operations on a state change, and an infinite tape. Seems like a syntax for that is quite formally describable (just a set of tuples for the state, the next state to jump to and the operation would do it.) With that syntax you have the ability to enumerate all possible turing machines; so you have a syntax for a turing-complete language. Turing completeness usually means an instruction set, or programming language, that can implement any turing machine… seems like my set-of-tuples could do just that (assuming the availability of infinite tape.) But - one can certainly write a unrestricted grammar that describes a recursively-enumerable language that is turning complete… and that would definitionally be a formal syntax description; just in the abstract. For example, the programming language Thue is itself Turing-complete, and its syntax is very simple (and easy to formally define.) I’m not sure how that applies to HLASM syntax though :-) - Dave R. -
