4 ms·

There are two problems with making that distinction. First, by that definition, few languages have regular expressions as a feature. Second, in languages with s

There are two problems with making that distinction. First, by that definition, few languages have regular expressions as a feature. Second, in languages with support for syntax rewriting, that would mean the internal implementation, not the user-facing syntax, is what decides what counts as a "real" feature.

kazinator 5y ago
A TM is a machine which accepts a tape, together with a specific tape: it performs a very specific calculation. A UTM can take an instructional input which turns it into a different machine, which can then process tapes designed for a different TM mechanism. A fixed programming language (and its standard library) is a UTM. If there are regular expressions in the language syntax, or the library, it's a feature of the UTM. Everything else is instructions: additional libraries, macros, whatever. We can extend languages by pretending that the additional code we have written (libraries, syntax rewriting) comprise a new, extended language. So that's a new UTM. There are limits in what syntactic rewriting can provide in a seamless, efficient way. Some features are simply not expressible in the target language of the rewriting, other than by using the syntax to create an inefficient, interpreted language. The use of the features it provides is walled off within the embedded syntax. (Not to deny that this is nevertheless valid and practically useful.) The UTM theory tells us that we can always adapt a UTM to accept the tapes intended for any TM mechanism. However, it doesn't tell us how costly that is. For some TM mechanisms, the approach may be to translate a given tape up-front into the UTM's own instructions and then run it directly. For some TM mechanisms, the approach may be to simulate the mechanism: the UTM's instructions execute the simulator, which executes the tape. The UTM theory mostly talks about simulation. What we know is given a Turing Complete language A (i.e. a UTM) we can always write an interpreter for language B. That's the baseline. We then have a new UTM equivalent to B, consisting of language A, plus the interpreter. That setup then accepts programs of language B, and their inputs.
- weavejester 5y ago
  > If there are regular expressions in the language syntax, or the library, it's a feature of the UTM. By "the library" do you mean the core library of the language? If a language didn't have regular expressions as part of its core library, does that mean regular expressions would not be a feature of that language? > Some features are simply not expressible in the target language of the rewriting, other than by using the syntax to create an inefficient, interpreted language. Why inefficient? Why interpreted? What if the syntax was efficiently compiled?

kazinator 5y ago

A TM is a machine which accepts a tape, together with a specific tape: it performs a very specific calculation. A UTM can take an instructional input which turns it into a different machine, which can then process tapes designed for a different TM mechanism. A fixed programming language (and its standard library) is a UTM. If there are regular expressions in the language syntax, or the library, it's a feature of the UTM. Everything else is instructions: additional libraries, macros, whatever. We can extend languages by pretending that the additional code we have written (libraries, syntax rewriting) comprise a new, extended language. So that's a new UTM. There are limits in what syntactic rewriting can provide in a seamless, efficient way. Some features are simply not expressible in the target language of the rewriting, other than by using the syntax to create an inefficient, interpreted language. The use of the features it provides is walled off within the embedded syntax. (Not to deny that this is nevertheless valid and practically useful.) The UTM theory tells us that we can always adapt a UTM to accept the tapes intended for any TM mechanism. However, it doesn't tell us how costly that is. For some TM mechanisms, the approach may be to translate a given tape up-front into the UTM's own instructions and then run it directly. For some TM mechanisms, the approach may be to simulate the mechanism: the UTM's instructions execute the simulator, which executes the tape. The UTM theory mostly talks about simulation. What we know is given a Turing Complete language A (i.e. a UTM) we can always write an interpreter for language B. That's the baseline. We then have a new UTM equivalent to B, consisting of language A, plus the interpreter. That setup then accepts programs of language B, and their inputs.

weavejester 5y ago
> If there are regular expressions in the language syntax, or the library, it's a feature of the UTM. By "the library" do you mean the core library of the language? If a language didn't have regular expressions as part of its core library, does that mean regular expressions would not be a feature of that language? > Some features are simply not expressible in the target language of the rewriting, other than by using the syntax to create an inefficient, interpreted language. Why inefficient? Why interpreted? What if the syntax was efficiently compiled?