One of the surprising aspect of the genome for lay-people is that itcontains important non-coding DNA parts, which does not mean that they areall useless. I never paid so much attention to the fact, until veryrecently, when I realized that the same is apparently true of allcomputing formalisms I can think of ... but maybe I forgot some, whichis part of my question.If you consider finite state automata, you can always add an arbitraryfinite chain of unreachable states, which may be read as the Gdelnumber of whatever statement you care to add to the FSA,whether a copyright statement or a complete formal proof that itrecognizes a regular expression in some a priori chosen formalism.But the same is actually true of CF grammars, of Turing Machines, ofPost Correspondence Problems, of lambda-expressions, of PrimitiveRecursive programs, or of Partial Recursive programs, to name some ofthe more important computing formalisms. Actually I cannot think of acomputing formalism that does not have that syntacticfeature. This is also true of programming languages, often as anofficial syntactic feature called comment, which is not strictlynecessary, but does save time and space.I recently used the property to prove (hopefully correctly) that allprimitive recursive functions can be implemented as a recursive set ofTuring Machines. This may not be a very deep result, but my understanding from that proof isthat the phenomenon is very general and may have other consequences.To be precise about definition, I think one could call non-coding partof a formalism instance those parts that can be identified by a uniformdecision procedure as computationally irrelevant.Question:Is the property as general as I make it? Has it been analyzed morethoroughly, including causes (is it unescapable?), consequences, andtheoretical or practical uses? Does it have a name?I think that the property could somewhat be implied by generaltheorems about computability. But why should that extend to verysimple formalisms like FSA.My guess is that, given the above definition of non-coding part, itmay be that for simpler formalisms like FSA there is a uniformrecursive procedure that can remove all non coding parts: thatprocedure could be made part of the formalism specification, thuscontradicting my universality statement. But such a procedure wouldnot exist for a Turing complete formalism (Rice theorem?). And the fact remains that even the simpler formalisms we use are defined with this comment potential, even if it might be removable by a restriction to normal forms.
A syntactic property of computing systems: is non-coding DNA universal?
computability;reference request;semantics;normal forms;syntax