[FOM] Simple Turing machines, Universality, Encodings, etc.

[Alexander Smith]

Looking through the message, it seems that some of my proposed definitions of universality (the second, fourth, and ninth) are accidentally too general, in that a suitable non-universal system can take input representing the rule of a Turing machine/tag system/cyclic tag system and a number of steps to emulate it for, and deduce its behaviour to that number of steps from anything; 'non-universal' is clearly too lenient a restriction here. The eighth definition does actually require some input representing the system in question, but still suffers from much the same problem.

The fact that I made this mistake shows that care in defining universality is needed, to make sure that the definition ensures that the universality resides in the system in question and not in an input or output mechanism. Definitions based on solving the 'halting problem', where 'halt' is redefined to make sense with respect to the system in question, seem at present more likely to avoid this particular problem.

Despite these problems with the specifics of what I've written in the quoted message, I still think that the general points I was making, and the specific points in the other sections of the message, are correct.

--
Alex Smith

  _____

From: fom-bounces at cs.nyu.edu on behalf of Alexander Smith
Sent: Wed 31/10/2007 13:49
To: pratt at cs.stanford.edu; Foundations ofMathematics
Subject: Re: [FOM] Simple Turing machines, Universality, Encodings, etc.


(snip)

Back to my original question: Is there at least one mapping function that makes the system I defined near the start of this message universal? I think that there is a third possible answer to this question that hasn't been discussed yet, which is "yes with some definitions of 'universal' and no with others". In this situation, the system is well-defined, and what sort of tape length and input can be used with the system is instead part of the definition of universality; how to deal with the lack of a halt state is another question that should be addressed here. In the below, a 'halting process' is a process that maps input to output and can be proven in advance to always generate a finite amount of output, followed by some signal that it's 'finished' generating output, in a finite amount of time. With this view (which seems conceptually neater and clearer to me, even though it's likely to be controversial), the question can be answered:
- no, if the system needs to be able to actually stop running, rather than just do something equivalent, as a necessary condition to be considered universal (the system can't halt!)
- no, with a finite-length solid-colour tape and the definition of what is considered universal behaviour is the same as in the first 'yes' point (this is pretty intuitive, as a universal system has to be able to support an infinite amount of data)
- no, if the tape consists of nothing but a finite-length encoding of the input produced by a halting process which has a length proportional to that of the input (i.e. 'linear bounded automata are non-universal'; this needs defining slightly more precisely because 'length of the input' is vague, but it could be made rigourous by specifying bits or other similar units of data; I'm being silent on the precise definition of universal behaviour needed for this point to be correct because I don't know how general it can be and still leave the answer as 'no')
- yes, if the tape is an infinite solid-colour tape, and the system is considered universal if the evolution of any Turing machine to any given number of steps can be deduced from the sequence of situations of the system by a process that can be proven in advance to halt (this shows that a system can be universal without input; I haven't proven this yet, but based on my programming experience it seems obvious to me that this is true; is it obvious to others? Is my intuition on this wrong?)
- yes, if the tape consists of a finite-length encoding of the input produced by a halting process which has a length proportional to that of the input surrounded by an infinite number of tape elements that are all the same colour, and universal behaviour is considered to be that for which the system is considered to 'halt' when it enters a situation that's the same as a situation it's previously been in and the system 'halts' for those inputs that represent with some suitable encoding tag systems which eventually halt, and doesn't for inputs that represent tag systems that don't (the original universal Turing machine is an example for this definition of 'universal'; again, due to imperfect knowledge, I haven't defined 'suitable encoding')
- yes, if the tape consists of an infinite number of repetitions of a sequence of elements A, followed by a sequence of elements B, followed by an infinite number of repetitions of a sequence of elements C, each of the sequences A, B, and C is deduced by a halting process, and universal behaviour is considered to be that for which the system is considered to 'halt' when it enters a situation that's the same as a situation it's previously been in, except for a possible translation of all elements and the active element, and the system 'halts' for those inputs that represent with some suitable encoding cyclic tag systems which eventually halt, and doesn't for inputs that represent cyclic tag systems that don't (yes because this is a generalisation of the previous definition because tag systems can be converted to cyclic tag systems by a halting process; I mention this definition because when applied to cellular automata rather than Turing-machine-like-systems, it's the definit!
 ion that allows rule 110 to be universal whereas I suspect none of the previous definitions do)
- yes, if the tape consists of an infinite sequence of elements all of which are generated from a finite amount of input by a non-universal rule, and universal behaviour is considered to be that where for some definition of 'halting' that can be calculated by a non-universal process from the sequence of situtations the system goes through, the system 'halts' for those inputs that represent with some suitable encoding cyclic tag systems which eventually halt, and doesn't for inputs that represent cyclic tag systems that don't (this definition allows the 2,3 Turing machine in question; one potential problem with it is recursive and shows no obvious way to bottom out, but luckily non-universality of a system with respect to any reasonable definition can often be proved pretty conclusively, like in the proof I gave for the 2,3 Turing machine)
- yes, if the tape consists of an infinite sequence of elements all of which are generated from a finite amount of input that represents with some suitable encoding a cyclic tag system by a non-universal rule, and system is considered universal if the evolution of that cyclic tag system to any given number of steps can be deduced from the sequence of situations of the system by a process that can be proven in advance to halt (this definition also allows the 2,3 Turing machine in question)

(snip)

- yes, if the tape consists of a (fixed and non input-dependent) infinite sequence of elements calculated by a non-universal process, and the system is considered universal if the evolution of any Turing machine to any given number of steps can be deduced from the sequence of situations of the system by a process that can be proven in advance to halt

(snip)