Talk:Stæck

BCT Interpreter

Nice language, and great work on the BCT interpreter! I've been looking at it, trying to understand how the intended non-erasing stack automaton the spec seems to be is TC. EDIT: I thought I'd found a bug, but after typing up the description and example then re-reading it, I saw my mistake in how I was converting the stack... nothing else concrete to say yet. Sorry! Salpynx (talk) 10:58, 1 June 2019 (UTC)

And in seeing that I was able to finish what I've been trying to do for ages now, get the Bitwise_Cyclic_Tag#Example BCT program to run as a concrete example. Starting at the second step because wrapping is not supported: program = 01110 data = 01 which converts to the Stæck BCT interpreter input 10111111100001.

./stæck.py -f bct.st 10111111100001 | head -n2000

with print('s-%s' % .join([str(n) for n in self.stack]).replace('11','A').replace('10','B').replace('00', ' ').replace('A', '1').replace('B', '0')) inserted into the Stæck interpreter to convert and print the BCT data at each step of Staeck.run() gives:

s- 01 110 1010 010 1010 010 1010 010 1010 010 1010 010 1010 010 1010 010 1010 010 10

Which looks correct. This interpreter seems skip some steps to save duplication (the previous version does include them), but I don't think that changes anything significant WRT TC. At least I hope not. Nice work on the proof! Now I still want to figure out why a non-erasing stack automaton is Turing complete.

As an aside, I wasted a whole lot of time by misunderstanding how input is passed to the python interpreter. It is taking the LSB of each 8bit int in the input sequence so any even number is equivalent to 0, and any odd number is equivalent to 1, i.e. input 9247 is equivalent to 1001. I wasted about an hour converting binary to decimal and using that representation as input to the BCT interpreter, and getting almost sensible results in some cases. LOL. Hopefully these examples will prevent anyone else from making the same error! Salpynx (talk) 11:54, 1 June 2019 (UTC)

The main reason Stæck is Turing complete, is because it is able to keep the stack pointer position while pushing bits. This allows for trivially copying portions of the stack back to the top. If & is made to reset the stack pointer to the top, it becomes Turing-incomplete; although I think it degenerates into a Finite state machine, and not a stack automaton. Weird. TuxCrafting (talk) 12:19, 1 June 2019 (UTC)

After re-reading the wiki page, it's not that weird after all. That section never claims stack automata are not TC, and the DSPACE complexity class only applies to Turing equivalent machines. Now I've looked at the referenced paper and it states nonerasing stack machines are TC in the abstract :) the wiki implies stack automata are less powerful than Turing machines because of its position in an article about PDAs. I wonder if 'stack automaton' = 'generalisation' of PDA, which is on the wiki, is accurate? Still, I like this, and following through the code proof instead of reading the paper was fun! Salpynx (talk) 19:31, 1 June 2019 (UTC)

I see. I read that section and got the idea for Stæck without reading the references, and as the wiki seemed to imply it's Turing-incomplete I assumed it was. Heh. TuxCrafting (talk) 21:11, 1 June 2019 (UTC)

UTF-8 multibyte character stream output mod

Replace sys.stdout.write(chr(c)) with sys.stdout.buffer.write(bytes([c])) in the provided Python interpreter to enable Unicode output in UTF-8, and serious programs like this Stæck steak counter:

 {'&{'.'.'.'.".".".".".".".".".'.'.".".'.".'.'.".'.".".'.'.".'.".'.".^}'.".'.".'.'.'.'.{v}}

Not sure how cross-compatible this is, which is why I am not editing the main page directly. Tested under Python3 and Ubuntu Linux. Salpynx (talk) 04:18, 3 June 2019 (UTC)