Talk:Qdeql

A revised Qdeql

(omission corrected later --Graue)

I am working on a revised Qdeql, tentatively called Sceql, with these commands:

= NEXT   Dequeue a byte and enqueue it again
- DEC    Decrement the byte that would be dequeued next (wrapping)
_ INC    Increment the byte that would be dequeued next (wrapping)
\ BEGIN  Skip to the instruction after the corresponding END if the byte
         that would be dequeued next is zero
/ END    Go back to the corresponding BEGIN
! GROW   Enqueue a new zero byte
& INPUT  Read a byte from stdin and enqueue it (0 for EOF)
* OUTPUT Dequeue a byte, write it to stdout, and enqueue it again

One difference from Qdeql, aside from the commands, is that the queue starts out with one zero byte in it, rather than starting out empty.

I think this instruction set may be usable for computation, but so far I haven't written anything useful with it. Here's a short program that prints an exclamation mark (ASCII 33):

!___________\-=___=/=*

Comments appreciated. --Graue 16:50, 20 Oct 2005 (GMT)

This instruction set is much better for computation, making it a LOT easier than in Qdeql.. Whip up an interpreter so we can try! :) --User:Keymaker

How's this? [1] --Graue 17:11, 20 Oct 2005 (GMT)

Here's a Javascript interpreter for Sceql. I've put an extra exclamation mark in front of the example Graue gave, as it needs a extra 0 in the queue to work properly. --Safalra 17:45, 20 Oct 2005 (GMT)

Oops, that was actually an omission in my specification of Sceql, not an error in the example! In Sceql the queue starts out having one zero byte, rather than being empty. --Graue 22:17, 20 Oct 2005 (GMT)

Woop, found an error in your interpreter. The * doesn't enqueue the byte after outputting it. --BodyTag 18:59, 20 Oct 2005 (GMT)

Okay, I've fixed it now. Thanks for pointing out the errors. --Safalra 10:16, 21 Oct 2005 (GMT)

By the way, what's the point of having one zero byte there initially? Since there's '!' it's rather easy just to add it. I'd suggest you to remove that initial zero byte, it's ugly. :p Anyways, gonna test this soon.. --User:Keymaker

Since the queue cannot shrink, the initial zero byte ensures that the queue is never empty. This removes the need for any special cases of the NEXT, DEC, INC, BEGIN, and OUTPUT instructions. --Graue 13:47, 21 Oct 2005 (GMT)

Hmmm, ok then. I guess that makes sense. --User:Keymaker

What is the official file extension? And, will you make a wiki page for this language? --User:Keymaker

File extensions are so last century. Seriously though, they confuse certain web browsers (some of which treat ASCII files without an extension as text that can be viewed in the browser, but ASCII files with an unknown extension as files that must be downloaded). --Safalra 15:34, 21 Oct 2005 (GMT)

Is Internet Exploder one of them? --Ihope127 19:00, 21 Oct 2005 (GMT)

You must be mistaken; only the web server can possibly be confused by a file extension. Web browsers merely rely on the content type passed on to them by the server. If the browser presents a text file as downloadable, then it is the server that is misconfigured. --Graue 23:41, 21 Oct 2005 (GMT)

Actually, a number of irritating web browsers ignore the content-type header from the server if it goes against what the browser thinks the extension should represent. I believe Internet Explorer is one of them (someone with Windows will have to check this). --Safalra 09:55, 22 Oct 2005 (GMT)

I don't know. Maybe .sq, unless that's already used for something else. --Graue 23:41, 21 Oct 2005 (GMT)

I don't think it is. Perfect excuse to make a language called Squeegee. --Ihope127 00:21, 22 Oct 2005 (GMT)

According to http://filext.com/ it is not used, though there probably is some program somewhere that uses it IMHO. But who cares? .sql would also be appropriate :) --Rune 00:39, 22 Oct 2005 (GMT)

Yep. I'm sure this language meets the description of "Squish Message Base Last Read Pointers" perfectly!

Bah, that website is useless. It doesn't even know that .t signifies a Thue program. --Graue 17:14, 22 Oct 2005 (GMT)

I made the example program on the Javascript interpreter to output a exclamation mark and make it copied many times and got this output:

!

� �OODDDDVV\\\\ŸŸtttt¬¬ŒŒŒŒÄĤ¤¤¤îî¼¼¼¼**LL22++Ĭ5Ä55ÌÌ++55””““$$««<<,,ggEEyy]´]]Ž¼ŽŽÄÄ++ÌÌ;;TT··OOÅŹ¹mmÁÁ++²²\\ Many of the characters are copied 2 or 4 times, some aren't. --Zzo38 14:02, 14 May 2006 (UTC)

What's wrong?!

I worked for one program for hours, tried to be as careful as possible, but then didn't get it working as it should. Is there something wrong with Sceql interpreter or have I understood something uncorrectly? Here's a test program that should output "320" but it does not (the numbers there are comments showing memory states):

0
!!
0 0 0
_____ _____ _____ _____ _____ _____ _____ _____ _____ ___
48 0 0
==
0 48 0
_____ _____ _____ _____ _____ _____ _____ _____ _____ _____
50 48 0
==
0 50 48
_____ _____ _____ _____ _____ _____ _____ _____ _____ _____ _
51 50 48
***
output: 320

What's wrong? --User:Keymaker

It outputs 320 in the online interpreter. What interpreter do you use? --BodyTag 14:35, 23 Oct 2005 (GMT)

You found a bug in my interpreter; sorry about that. It's fixed now, at the above link. By the way, if you compile the interpreter with "#define DEBUGGING" (or use the -DDEBUGGING option with gcc), you can use ` as a "print memory state" instruction. --Graue 17:07, 23 Oct 2005 (GMT)

Ok, cheers. I'll download the new version of the interpreter today and try if my program works now. --User:Keymaker

The interpreter gives me a segmentation fault during the execution of my program. So, there is probably another bug somewhere in the interpreter. --User:Keymaker

I think I fixed it; try the above link again. --Graue 15:22, 24 Oct 2005 (GMT)

Computational class

"Qdeql is Turing-complete, as brainfuck with a fixed number of unbounded non-negative cells can be reduced to it."

The same argument has been used before to show that TLWNN is Turing-complete. However, does anybody have a proof that said variant of BF is Turing-complete? Or has somebody just assumed it because BF and Minsky machines are? — Smjg (talk) 21:14, 15 March 2012 (UTC)

See Collatz function for the proof that three-cell brainfuck is TC. Ørjan spent quite a while proving this some months ago. —ehird 21:44, 15 March 2012 (UTC)

It is also relatively obvious that unbounded-nonnegative-cell BF can simulate Minsky machines by adding just a few extra cells (one for the machine state, at most a couple to handle control flow.) In fact I started out by modifying the 2-cell Minsky machine construction I found on Wikipedia. Doing it with just one extra cell is what gave the limitations on control flow that led to Fractran and Collatz functions. --Ørjan 23:06, 15 March 2012 (UTC)

Single-byte queue?

The preceding point aside, I have trouble believing any language with only a single-byte memory space can be TC. Moreover, the claim that \ "enqueue the byte again, followed by two zero bytes" doesn't make sense when the queue's capacity is just a single byte. Or does it actually mean something else, like a single queue of bytes, or a queue of single bytes? — Smjg (talk) 21:14, 15 March 2012 (UTC)

Single (byte queue), i.e. single queue of bytes is the obvious meaning given instruction descriptions like "Dequeue a byte and enqueue it again". It's also implied by the original specification and is what the reference implementation does. I've reworded that phrase to make it clearer. —ehird 21:43, 15 March 2012 (UTC)