3

"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?

the Tin Man
  • 158,662
  • 42
  • 215
  • 303
tuskiomi
  • 190
  • 1
  • 15
  • 2
    I’m voting to close this question because "[softwareengineering.se]" is a better site for this. – the Tin Man Jun 14 '20 at 23:59
  • @theTinMan firstly, if you don't think the question is appropriate, the vote to close is the incorrect feature to use. You flag it for moderator intervention, and you put in the box the site that you want it migrated to. – tuskiomi Jun 15 '20 at 00:02
  • @theTinMan secondly, doing it the correct way, software engineering would likely reject the migration, as it has nothing to do with strategies related to writing software. – tuskiomi Jun 15 '20 at 00:03
  • This question is too old to be migrated. – pppery Jun 15 '20 at 00:22
  • Questions can't be migrated more that 60 days after they are posted. – pppery Jun 15 '20 at 00:27
  • Say what you want, but the [Help Article](https://softwareengineering.stackexchange.com/help/on-topic) has *nothing* on what this question asks, and as a matter of fact, the site says specifically that "Explaining, writing or debugging code" can "appear to fit into one of the above categories, [but] may still be off-topic". I don't know how somebody got the idea that Software engineering is a better site. Much more prominent, just because one site may be better (in this case it isn't), that doesn't meant that another is wrong. – tuskiomi Jun 15 '20 at 00:35

2 Answers2

2

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.

the Tin Man
  • 158,662
  • 42
  • 215
  • 303
0

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.

JMW
  • 261
  • 2
  • 7
  • Good info.. doesn't answer the question. – tuskiomi Jun 14 '20 at 20:30
  • I can't answer the question to your satisfaction. I answered why your language, if it does what you require - i.e. prevent the outputting of a quine, is not Turing complete. Now if you ask "given that the language is not Turing complete, but errors on an empty program, is it now Turing complete?", that extra language feature cannot change my answer in any way. – JMW Jun 17 '20 at 00:45
  • I think you are overthinking this. It's really simple: how to make a program unable to output it's own source: 1) don't print anything until execution finishes without interruption. 2) if the execution finishes, take a sha-512 hash of the print, and compare it with a sha-512 hash of the source. If the hashes are equal, print nothing. 3) if an empty program is to be compiled, throw an error. – tuskiomi Jun 17 '20 at 00:50
  • in the case of a quine, it is only a quine if the program uses no outside sources to help it. Use of external libraries in a quine is not a true quine, so external libraries are not an issue. – tuskiomi Jun 17 '20 at 00:52
  • there's no problem with building a compiler in it's own language, as any compiler must also follow the rule where quines cannot be printed. Of course, this compiler could even compile itself! It's a compiler! I think what you mean, is that a decompiler could not decompile itself. – tuskiomi Jun 17 '20 at 00:56
  • No. I don't mean anything like that. If your language can compile the source code for an interpreter for an arbitrary language, then it can compile an interpreter for a language that ONLY decodes an encoded form of the source code for your 'Language X'. If your language can not be used to create an interpreter for an arbitrary Turing complete language, then it's not Turing complete. So your 'Language X' is either not Turing complete, or it emits quines (and with no external libraries needed, either). There is no room in between. One or the other statement holds. – JMW Jun 17 '20 at 03:25
  • And no, trapping the output sent to the screen doesn't work either. Your monitor doesn't work that way, and buffers don't help either. Can your language do I/O at all? A quine emitted by any I/O channel counts as a quine. If your language can't do I/O of any kind than it's not Turing complete. If your language can 'return' a value than that counts. Can't return a value by any means? Than it's not Turing complete. There is no room in the middle. You must pick one. You can have a Turing complete language, or you can have a language that cannot emit quines. Not both. – JMW Jun 17 '20 at 03:29
  • making an interpreter which gets around this is not an interpreter for the language in question. My language (Lang M) users the same syntax as the interpreter, but it is not your language ( Lang L ), because L can print quines. – tuskiomi Jun 17 '20 at 03:39
  • you're *really* overthinking this, and I'm starting to doubt your knowledge of memory management in common PC architectures. Virtualization is trivial in this day and age. – tuskiomi Jun 17 '20 at 03:43
  • Can't simulate 'Language L'? -- Not Turing complete. See the definition on this page: https://en.wikipedia.org/wiki/Turing_completeness "In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally universal if it can be used to simulate any Turing machine." – JMW Jun 17 '20 at 04:11
  • I never said that it couldn't. – tuskiomi Jun 17 '20 at 04:12
  • Ah, ok. 'Not in your language' -- 'Language L'. I get your point now. But 'Language L' is a specialized language designed only to defeat your 'Turing machine that can't output its own source code'. And if you make this conversation about virtualization than it's no longer about computability theory. A Turing machine that outputs the source code for 'Language X' is a Turing machine. 'Language L' is a Turing machine that emits the source code for 'Language X'. Can't simulate 'Language L'? Than Language X is not Turing complete. Virtualization simply has nothing to do with it. – JMW Jun 17 '20 at 04:28
  • The long answer is great, but I can implement a turing machine on my language M, as a matter of fact, I've implemented a mach-up on my PC just to make sure it is valid, it is in the form of a brainfuck interpreter. If M can implement a turing machine, it is turing complete, no? – tuskiomi Jun 19 '20 at 05:01
  • Simulating one Turing machine does not imply Turing completeness. Turing completeness implies the ability to simulate _any_ Turing machine, including an infinite number of Turing machines that are unable to function properly unless they are able to verifiably output (by Turing standards - IOW, to their own internal data store) a copy of the source code to language M. – JMW Jun 21 '20 at 05:20