[FOM] Nested-universality

[Alexander Smith]

I've been trying to pin down the precise definition of universality that I used in the 2,3 proof, and have come up with the concept of nested-universality (a generalisation of previous definitions), at least in determining what sort of initial conditions are allowed. (I haven't yet come up with a definition of what sorts of things should be allowed to detect a halt-equivalent state.) The online version of the proof doesn't quite show that it meets this definition, but I'm pretty confident an improved version of it could be worked out that does. (I have most of the details in my head, but haven't done it rigorously yet.)
 
The idea is to specify precisely what sorts of method can be used to generate the initial condition; for nested-universality, this is a two-step process. First, the system being emulated (in the case of my proof, a cyclic tag system) is translated into the rules for a 'self-embedding one-counter neighbour-independent substitution system' (a concept that I think I've invented, and will explain later in this email); this can be by any process that produces a finite amount of output, which is known in advance to halt in a finite amount of time, and which can be simulated by a Turing machine. (Is this a suitable definition for the first part; I don't think there's a way to exploit this definition to produce universal behaviour with this step by itself, or combined with the next one, without using an oracle (which I've specifically banned here), but have I let too much through?) Then, that system itself is run, producing successive outputs, each of which contains the previous output; the limit of the sequence of such outputs (which due to the nature of such systems must exist, but could be finite, semi-infinite, or infinite) forms the initial condition for the system whose nested-universality is being established. (This definition limits inputs to being one-dimensional and would need to be generalised to deal with universality in systems whose input wasn't one-dimensional.)
 
A one-counter neighbour-independent substitution system consists of an initial list, a set of rules for rewriting lists, and a set of rules for translating those into the input expected by the nested-universal system candidate. The lists consist of elements, where each element consists of a symbol taken from a finite alphabet (different one-counter neighbour-independent substitution systems can have different alphabets, and there can be any number of symbols but there must be a finite number), and a nonnegative integer (with no upper bound). Any list can be used as the initial list in the general case, but for the system to be self-embedding, the list must contain exactly one element. There are, in every case, stronger restrictions on what is allowed as a rewriting rule. There must be two rewriting rules for each symbol; a rule for rewriting an element with that symbol and 0 as the accompaning integer, and a rule for rewriting an element with that symbol but with a positive integer; a rule can be omitted if it can be proven that it never becomes relevant. The rules replace the element they're replacing with a new list, and the resulting lists are concatenated to form the resulting list at the end of the step; the symbol of each element in the new list is specified literally by the rule, but the only options for the integer in each element are one higher, the same as, and one lower than in the element being replaced (a different option can be chosen for each element in the replacement list; the one-lower option can't be used for a replacement for an element with 0 as the integer). So at each step, all the elements in the list are replaced by new lists.
 
One-counter neighbour-independent substitution systems are obviously (to me, anyway) not universal by any reasonable definition. Because there is no interaction at all between different elements of the list, each acts like a one-counter machine, which are known not to be universal if increment/decrement are the only operations allowed on the counter (which is ensured by the restrictions on the nature of rewriting rules). The machines can split into multiple machines, that is become multithreaded, but there is no communication between threads, so overall the system can have no more computational class than a nondeterministic one-counter machine and cannot be universal.
 
A one-counter neighbour-independent substitution system is defined to be self-embedding if their initial list contains one element, and the replacement for it contains exactly one copy of that element itself (that is, the same symbol, and 'the same integer' as the option for the integer on that element). The list for such systems after each step must contain the list for the previous step as a substring, due to the nature of the self-embedding systems (because it's what the self-replacement after the first step eventually expanded into); therefore, it's possible to take the limit of such lists to produce a list-in-the-limit that's infinitely long.
 
The translation rules are the final part of a one-counter neighbour-independent substitution symbol; they simply expand each element in the list into a (possibly empty) string of colours/elements/symbols/whatever in the initial condition being generated for the possibly nested-universal system. The string each element expands into is fixed for each possible symbol, and depends only on that symbol.
 
Because I'm an engineer and programmer, rather than a mathematician, I went and implemented these systems as a programming language, with a defined syntax; see http://esolangs.org/wiki/1cnis. That page contains the syntax for the language, as well as examples and implementations.
 
Anyway, what I want to ask is: do FOM posters think that this is a reasonable generalisation of the traditional definition of universality (placing the identifying-a-halt-equivalent-state problem to one side for the time being)? This definition meets my intuitive idea of what universality ought to be (that is, that a system is in some respect capable of doing any calculation itself, using other rules merely to help set it up and to give instructions), even if it allows some systems that are not universal by the traditional definition. (Generalising a definition is almost certain to allow new systems to fall under it; I would be happy but surprised if it turned out that nested-universality was equivalent to traditional only-finitely-many-nonblank-tape-elements universality.) I'm just worried that I may have made a mistake in this definition that admins some systems that obviously ought not to be universal even in a generalised sense. (It definitely doesn't allow linear-bounded automata because they can only take a finite amount of input and the halting problem can't be solved by a known-to-terminate Turing machine (or by any Turing machine, for that matter), so there's no way to set them up to halt iff the system being emulated halts.)
 
I haven't yet proven that the 2,3 Turing machine is nested-universal, but I'm pretty sure that it is (I have an outline proof in my head, but I'm quite busy and haven't yet had time to work out the details in rigorously). An advantage of the new initial condition I'm thinking of is that it has a very simple halt rule (the initial tape is semi-infinite; it terminates at the left, and the tape head falls off the left-hand end of the tape if and only if the cyclic tag system being emulated halts. It would be possible to fill the whole of that section with orange if semi-infinite tapes aren't allowed, so that the tape head would instead zoom off to infinity leftwards if the system being emulated halts; and if actual halting is needed you can just add a fourth colour to make a 7-rule 2,4 Turing machine with a halt rule, or 7-rule 3,4 Turing machine with a halt state).
 
-- 
Alex Smith