Is a language built specifically to not print quines still Turing complete?

Question

"Is it possible to create a quine in every turing-complete language?" says that:

Any programming language which is Turing complete, and which is able to output any string (by a computable function of the string as program — this is a technical condition that is satisfied in every programming language in existence) has a quine program (and, in fact, infinitely many quine programs, and many similar curiosities) as follows by the fixed-point theorem.

If I created Language X that has the following output handler:

public void outputHander( OutputEvent e ){
  String msg = e.getMessage();
  String src = Runtime.getSource();
  if( msg.equals(src) ){
    e.setMessage("");
  }
}

This prevents the source from being output in any way.

If the interpreter for Language X was checking for its source at all times on the screen and the source was found, it's deleted before it hits the screen.

Given that an empty program will throw a non-blank error, is Language X still Turing complete? Why?

Answer 1

Although a quine can be prevented, it can still, possibly, simulate Turing-complete algorithms that don't require I/O. The Turing-completeness of Language X is unknown.

Answer 2

How can you prove your language cannot be tricked into outputting its own source code? To make this work, your language can't have any way to run external programs, otherwise, it could accidentally be made to send a suitably encoded version of its source code to a command-line tool, like uuencode or rot-13 or something. Just about any UNIX tool could act as a decoder.

Your language won't be capable of running itself either, it can't be an interpreter, it has to be a compiler. Otherwise, it could modify itself to output its own source code. On top of that, your compiler can't be useable for creating an interpreter in an arbitrary language, otherwise, you'll have a quine on your hands.

And once you've crippled the language so that it can't be used to create an interpreter in an arbitrary language, it's hard to see in what sense you would call it Turing complete at that point. In order to be provably crippled from ever outputting a quine, your language has to be extremely weak by Turing standards, and certainly not Turing complete.

EDIT - The conversation has begun to resemble the old argument about how many angels can be placed on the head of a pin. So, I will attempt to settle the question in a rigorous way. Virtualization is not relevant because a Turing machine is an abstract model of a computational device, and the only I/O that's implemented on the original Turing machine model is a movable tape upon which symbols get printed. The same tape is used as the memory - both for data and for the program store. The whole conversation seems to hinge on whether a Turing machine has to be able to output an arbitrary string in order to qualify as Turing complete. I will prove that it does by defining a Turing machine (Turing machine L) that outputs the source code of Language X. A machine that merely compiles code might not qualify as Turing complete, as that code may never be run. So we will define the implementation for Language X to be an interpreter rather than a compiler.

There is a natural question about whether outputting the source code for Language X counts if it's mixed with program code / other data / other output. So we will define this Turing machine to have a zero point on its tape. Anything to the left of the zero point is either code or data. Everything to the right of the zero point is for output. Turing machine L has a number (infinite) of different implementations. But they all have a predefined code section that can contain zero or more bytes of program code and/or data.

It is in all respects a normal Turing machine with a normal set of instructions, except that the instruction that adds two numbers is implemented in a special way. The code for this instruction actually contains a suitably encoded version of the source code for Language X. Under normal circumstances, the adding functionality behaves as usual for a typical Turing machine. But whenever the tape head encounters the string "Happy birthday to you..." in the data section, the addition instruction behaves differently. In this case, it prints out the decoded source code to Language X in the output section of the tape. "Happy birthday to you..." can exist in the code/data section of the tape just fine without triggering the alternate behavior of the addition instruction. It's only when the tape head actually encounters "Happy birthday to you..." that the alternate behavior is triggered. This means that Language X has to solve the halting problem in order to prevent Turing machine L from outputting the source code to language X without otherwise altering its behavior - which it can never do. Language X has to be able to run (simulate) Turing machine L in order to qualify as Turing complete. And that means that if Language X is Turing complete, then it must be capable of running some infinite number of Turing machine L implementations that output the source code to Language X, and can't interfere or it would fail to properly simulate Language X.

Now, it's still valid to ask whether merely erasing the outputted string from memory qualifies as preventing Turing machine L from forcing Language X (supposed to be Turing complete) to output its own source code - while maintaining the Turing completeness of Language X . I maintain that it does not - and I will prove this too. We will simply define a derivative of Turing machine L: Turing machine L'. This one is almost the same as Turing machine L, and like Turing machine L it comes in a number of different implementations. The only difference is that Turing machine L' comes with a mechanism for verifying the integrity of its output section. If the tape head encounters "Happy birthday to you..." then in addition to triggering the alternate behavior of addition, a special register called the "happy birthday register" flips its bit from 0 to 1 (it can flip back too). With this bit flipped, Turing machine L' will read the output section of the tape looking for the decoded source code to Language X. If it finds it, everything behaves as normal. But if it does not, then the machine's JZ (jump if zero) instruction will behave differently (it will move the tape head in a much less predictable fashion, much as though it were malfunctioning) - but only once the "happy birthday register" has flipped back. Additionally, whenever this verification fails to find the needed source code, the addition instruction will behave erratically as well, sometimes doing addition, and sometimes using the alternate behavior of outputting the source code to Language X. Now, because by erasing the output of Turing machine L' (the source code for Language X) you have changed it's behavior, you now have to solve the halting problem in order to properly simulate it while still erasing the source code to Language X every time it appears. And this is impossible. Even worse, Language X cannot know in advance how Turing machine L' is implemented , as there are an infinite number of valid implementations of Turing machine L and Turing machine L'. So Language X must choose between being Turing complete and refusing to output its own source code. It cannot do both.

EDIT2 - Another proof. A Turing machine is defined as a machine having a symbol tape, a non-empty set of symbols, and a non-empty set of transition functions (instructions) defined on subsets of those symbols (moving the tape, adding, multiplying, whatever). A Turing machine is Turing complete if it can simulate any other Turing machine. A Turing machine could be defined as having just two symbols and could still be Turing complete. For example, those symbols could be <blank> and 1. Now let's say that we take any fully functional Turing machine (an infinite number of Turing machines, some Turing complete, some not) defined with symbols <blank> and 1, but instead of 1, we use the source code to language X. So this Turing machine could do any task, in principle. It could calculate fibonacci numbers, print "hello world", play chess, calculate the orbital parameters for satellites in orbit, etc, etc. And whenever it does any of these calculations, it outputs (to its internal data store) some number of copies of the source code to language X, separated by blanks. Language X is either able to simulate this entire class of Turing machines, or it's not. If language X can simulate this entire class of Turing machines, then it could be Turing complete. If it can't then it is not. Every Turing complete machine can simulate every Turing machine in the entire possibility space of Turing machines. An uncountable infinity of Turing machines.