Talk:CHIQRSX9+

While I don't object to this joke line being in the specification:

• X Makes the programming language Turing-complete

Can it really be used to justify putting the language in the 'Turing Complete' category? --Safalra 19:28, 3 Aug 2005 (GMT)

Agree, maybe it shouldn't be categorized as Turing-complete. I don't understand Perl but looks like the interpreter doesn't make the language Turing-complete, at least I'd think so. Besides, there's no point being Turing-complete if can't execute programs for example to test the Turing-completeness. As well, how interpreter could even change that language Turing-complete? :) Well, it's joke afterall. --User:Keymaker

I haven't used Perl either, but it looks like when it encounters the X command it generates a random number and then shifts each remaining character through the character set by that amount, and evaluates the result. This is not only nondeterministic, but it's unclear whether any useful computation could be carried out in Perl by a shifted version of characters from the set {C,H,I,Q,R,S,X,9,+} --Safalra 09:58, 4 Aug 2005 (GMT)

I don't think the characters from the set CHIQRSX9+ have to be used for the remain of the program if X command is used, any characters can be used. Either way, if you are lucky and random number = 0 then the program will run as normal Perl code, but with a X at the beginning. But there is a 255/256 chance that it does NOT happen that way. (I'm not sure what to do about this, but I know Perl does a lot of things, so maybe you can use it like that!) --Zzo38 03:39, 20 Sep 2005 (GMT)

Ah. Probably not, and making it Turing-complete would require "infinite" memory as well (IIRC). I doubt those commands can access any memory, not to mention modifying it, or doing things like conditional loop or jumps that'd be very necessary. :) Perhaps I should take off its Turing-complete categorization? What do you say? --User:Keymaker

Good question. According to the spec it is Turing Complete, but the spec is not complete, as it doesn't say how this is achieved. But since the interpreter doesn't seem to be TC I'd say remove the cat.--Rune 21:48, 10 Aug 2005 (GMT)

Erm... Is it possible that it means to interpret the rest as Perl? 24.46.152.130 20:38, 17 Sep 2005 (GMT)

Then again, I know zip about Perl. Sorry 24.46.152.130 20:42, 17 Sep 2005 (GMT)

Oh. Apparently, it just executes random stuff, which might coincidentally work. 24.46.152.130 20:48, 17 Sep 2005 (GMT)

...Yeah, I think it'd be possible to execute it as Perl... maybe :-) (And do you mind if I unstrike your strikes?) --Ihope127 21:54, 17 Sep 2005 (GMT)

To be more precise, what X does is shift the input string by (rand 256), mod 256, and tries to execute the result as perl code. I haven't checked to see if any non-trivial program is theoretically possible with this, but I don't think it can be considered turing-complete, simply because for all intents and purposes it is non-deterministic, and most of the time in fact will do nothing. --24.198.49.77 22:10, 17 Sep 2005 (GMT)

Aha, thanks for clearing up what it does.. In that case it probably could be Turing-complete in that specific interpreter. In case the random instruction in that interpreter has always the same seed, and thus creates always the same values, then one could generate a source of a Perl brainfuck interpreter, for example. But if language itself is not Turing-complete, but the specs tell some instruction to change the program Turing-complete (but don't define how to do so), can that kind of language be truly considered TC? Can a language be so much interpreter-dependant? --User:Keymaker

It seems to me that the failure for the instruction to explicitly denote HOW the instruction makes it TC as well as how the interpreter executes the instruction makes it very NOT Turing-complete since it fails the "arbitrary effect at an arbitrary point" criterion. Its a pretty ironic instruction, in that respect. Almost zen like in its simplicity. Consider the question, "If a tree falls in the forest, is it a fish?" --Wildhalcyon 12:54, 29 Sep 2005 (GMT)

The way I thought was to try to implement the X command in such a way that it "makes" the language Turing-complete, but still the original language isn't, that is of course the point of the joke. Therefore in the implementation, the X command switches to a random choice of 256 possible Turing-complete languages. --Ørjan 18:10, 22 Feb 2007 (UTC)

I wonder if there's a polyglot that does something legal in all of them? ais523 18:19, 22 Feb 2007 (UTC)

Well, eval("") seems to be legal Perl. For anything longer, it seems hard to avoid some shift being a syntax error. --Ørjan 18:39, 22 Feb 2007 (UTC)

There's one very easy way to make the language TC (well, one I can think of): Implement the U combinator (see here) as your X operation (well, define X's behaviour as that of the U combinator in the spec). That way, not only can the language implement easy quines, cats, helloworlds, and whatnot, but it can actually do other stuff too. --Moopli (talk) 23:33, 3 August 2012 (UTC)