PDAsephtwo

PDAseptwo is an extension of PDAsephone by User:BoundedBeans, made in January 2025.

Storage

PDAsephone normally has two stacks, a stack of characters and a stack of instances of push-down automata. Each push-down automaton has a stack of characters, a current state, which is a character, and a mapping of state/stack/input character triplets to transitions. A transition is composed of a boolean value (whether to pop from the stack), a character to push on the stack, and a state to change to. Notably, the newline character cannot occur on the stack, and is only used to signify an empty stack or not to push anything.

PDAsephtwo has all this, but also a bit more.

• There is now also a queue of push-down automata. There is no queue of characters, but you can store characters inside of push-down automata, or use two stacks.
• Characters are now standardized to be 16-bit Unicode codepoints. This means that there is no handling for characters outside the Basic Multilingual Plane, and surrogate characters are handled separately. Also, every character actually used in PDAsephtwo storage objects has both the main codepoint and an arbitrary-length string of codepoints called the "diacritics". These can be any 16-bit codepoint; they are not restricted to only actual diacritical marks or combining characters, though the ones in the main Combining Diacritical Marks block from U+0300 to U+036F can be typed directly while others need to be constructed from commands.
• There's a map of characters that have main codepoints from ABCDEFGHIJKLMNOPQRST and a non-empty diacritic string, to strings of characters. These are used for custom commands, and the strings will be executed when an equal character is encountered in a command string.

All of this is now stored in an "execution environment". Execution environments can now be attached to a push-down automaton instance, replacing its normal storage and allowing custom behavior. When an execution environment is stored in a PDA, the execution environment containing that PDA is referred to as the "parent".

Syntax

Syntax now follows a more rigid structure. Since diacritical marks can be part of a command, there is now a new way that characters are parsed, following this procedure in order or something equivalent:

1. The code is read line by line using some input mechanism. Each line is considered separately. At this stage it is considered as a string, not as a sequence of commands.
   • This means that " commands cannot use a newline as an argument (use _ for that). Technically, " is a character by itself and its argument is considered a separate command when parsed, but is skipped by the " command.
2. Whitespace is trimmed from the start and end of each line.
3. If a line is equal to >>>>[, then everything up to a matching line equal to >>>>] is removed). These match like brackets, and can be nested. This is a multiline comment mechanism.
4. For each line, any instances of the regex >>>>@[^@]*@ are removed.
5. For each line, if the line contains the text >>>>, then that and everything following it is removed.
6. Each line is grouped into matches of the regex [^\u0300-\u036F][\u0300-\u036F]*. The matches are then converted into character instances with the first character as the main codepoint and the rest as its diacritics. Other character diacritics can be constructed with commands.

Common operations

When this specification says to pop a "terminated decimal", it means to pop a series of Latin decimal digits 0-9, terminated by a semicolon (ignoring diacritics for all of these), and interpret it as a number.

When this specification says to pop a "string", it means to pop a series of . characters with diacritic strings composed of a first character representing a main character, and the remaining characters (if any) representing a diacritic string, terminated by a ; character. This is interpreted as a string of characters.

If the stack is popped when empty because of missing arguments, the PDA-stack is repeatedly popped until it either becomes empty, or a PDA with an execution environment is at the top of the stack. If the PDA-stack is empty after this, the program exits. Otherwise, "@! gets run as an error-catching mechanism, then the program continues from there.

Commands

Lowercase letters from a to t with non-empty diacritic strings are reserved for extension commands.

@	Pushes a new pda onto the pda stack. It will have an empty stack, no transitions, will be in state '0', and will not have an execution environment.
%	Pops u, v, w, x, y, and z off the character stack. Installs the transition on the top pda: If input u, state v, and stack returns w, pop if x isn't 0, push y unless y is a newline, change state to z. Newlines can be used to not push anything. Errors: If the PDA-stack is empty, weird-goto Q.
!	Run a transition on the top pda, with input of the top character on the stack, popping that character Errors: If the PDA-stack is empty, weird-goto Q.
^	Pop a character off of the stack of the top pda, push it onto the character stack. If the pda's stack is empty, push a newline. Errors: If the PDA-stack is empty, weird-goto Q.
.	Print the top character on the character stack to the console
,	Input a character, push to the character stack
"	Move the instruction pointer 1 forward, and push that character onto the character stack. In other words, push the following character.
_	Push a newline onto the character stack
v	Pop a character off of the character stack, push it onto the top pda's stack. If the character is a newline, push a space instead
:	Duplicate the top element on the character stack
;	Duplicate the top element on the pda stack. Note: If pda's are references in your implementation, this operation should copy the contents. They should not reference the same object; changing one should not change the other Errors: If the PDA-stack is empty, weird-goto Q.
/	Swap the top two characters
\	Swap the top two pdas Errors: If the PDA-stack has only 1 element, weird-goto Q. If the PDA-stack is empty, weird-goto R.
¥	Pop a character A that is either + or -, pop a terminated decimal B. If A is +, move the top element on the character stack B places down. If A is -, move the Bth element from the top of the character stack to the top. Errors: If A is not + or -, push everything already popped back, weird-goto Q. If no valid terminated decimal was found, push everything already popped back. Push 'A' if this is because of not finding a semicolon, or 'B' if this is because of a malformed number. Weird-goto R. If the character stack doesn't have enough elements to roll, push everything already popped back, weird-goto S.
¶	Pop a character A that is either + or -, pop a terminated decimal B. If A is +, move the top element on the PDA stack B places down. If A is -, move the Bth element from the top of the PDA stack to the top. Errors: If A is not + or -, push everything already popped back, weird-goto Q. If no valid terminated decimal was found, push everything already popped back. Push 'A' if this is because of not finding a semicolon, or 'B' if this is because of a malformed number. Weird-goto R. If the PDA stack doesn't have enough elements to roll, push everything already popped back, weird-goto S.
$	Discard the top character
#	Discard the top pda Errors: If the PDA-stack is empty, weird-goto Q.
|	Weird go-to. This pops the top character off of the stack. If it is a capital letter, move the instruction pointer forward until that character is reached not following a " command (if it runs into the letter following quotes, it will continue looking). If it is a lowercase letter, move backwards. You will need to use multiple of these to get around sometimes. Only the letters ABCDEFGHIJKLMNOPQRSTabcdefghijklmnopqrst with no diacritics can be used as standard labels (20 in each direction). QRSTqrst may be used as error returns for official commands, but you can use them for your own purposes as well.
+	Make a reference to the top PDA on the stack, and push it (don't pop the original). References can have the same exact commands applied as normal PDAs, and for all intents and purposes are considered regular PDAs. Any changes made to this should apply the same changes to all things that reference the same PDA. Errors: If the PDA-stack is empty, weird-goto Q.
u	Pop a terminated decimal. If it is in the range 0-65535, push the character with that as the Unicode code-point. Errors: If the terminated decimal isn't successfully popped, push everything already popped back. Push 'A' if this is because of not finding a semicolon, or 'B' if this is because of a malformed number. Weird-goto Q. If the number is greater than 65535, push everything already popped back and weird-goto R.
U	Pop a character A and a character B. Add B to the end of A's diacritic list, deleting any pre-existing diacritics in B.
?	Pop a character, run the command corresponding to it.
Ù (U with diacritic string [U+0300])	Pop a character A, push a character with main codepoint . and a diacritical string composed of A's main codepoint followed by A's diacritic string.
Ú (U with diacritic string [U+0301])	Pop a character A and a character B. Push a new character with A's main codepoint and B's diacritic string.
Û (U with diacritic string [U+0302])	Pop a character A, which should be a . character as described in the Ù (U with diacritic string [U+0300]) command. Converts it into its full form, like undoing the aforementioned command. Errors: If A is not a . character, push it back and weird-goto Q. If A is . with empty diacritics, weird-goto R.
Ũ (U with diacritic string [U+0303])	Pop a character A, push A with the first codepoint in the diacritic string removed, push the codepoint that was removed. Errors: If A's diacritic string is empty, push A back and weird-goto Q.
W	Pop a PDA, push its state.
w	Pop a PDA and a string. For each transition in the PDA, push u, v, w, x, y, z in the same format as the % command uses (with 1 as the opposite of 0 used by x), and run the string. Errors: If the PDA-stack is empty, weird-goto Q. If one of the strings has an invalid character while popping, push everything already popped back on, push a digit from 1-6 depending on which string had an error, weird-goto R.
V	Pops a PDA, and pops 6 strings, A1, A2, A3, A4, A5, and A6. A1 becomes the function run on PDAs as %, A2 becomes !, A3 becomes ^, and A4 becomes v, A5 becomes W, and A6 becomes w. %: u, v, w, x, y, and z are pushed (as defined in the % command), and this string is run. !: The character on the stack is pushed (as defined in the ! command), and this string is run. ^: This string is run, then a character is popped off the character stack in this execution environment and pushed to the parent. v: Push the character on the stack (as defined in the v command), then run this string. W: This string is run, then a character is popped off the character stack in this execution environment and pushed to the parent. w: This string is run. Then, a terminated decimal is popped of the stack. Then, that many times, it pops 6 characters off the stack and runs the string given to the w command in the parent. Errors: If the PDA-stack is empty, weird-goto Q. If one of the strings has an invalid character while popping, push everything already popped back on, push a digit from 1-6 depending on which string had an error, weird-goto R.
¢	Pop a PDA, push the 6 strings in the same order (it should not be reversed) as V. Errors: If the PDA stack is empty, weird-goto Q. If the PDA doesn't have an attached execution environment, push the PDA back and weird-goto R.
X	Pop and enqueue the top PDA to the queue. Errors: If the PDA-stack is empty, weird-goto Q.
x	Dequeue a PDA from the queue and push it onto the PDA stack. Errors: If the queue is empty, weird-goto Q.
Ū (U with diacritic string [U+0304])	Pops a character A with main codepoint from ABCDEFGHIJKLMNOPQRST and a non-empty diacritic string, pops a string B. Maps this as a custom command. The characters %!^vWw with empty diacritics can also be used to modify the strings of the current PDA's execution environment. Errors: If A is not a valid custom command character, push everything already popped back, weird-goto Q. If an invalid string element was encountered while popping B, push everything already popped back, weird-goto R.
U̅ (U with diacritic string [U+0305])	Pops a label character. Tells the parent execution environment to weird-goto that label when it gets returned to.
Ŭ (U with diacritic string [U+0306])	Pops a custom command character, pushes the string it's mapped to. Errors: If the character is not a valid custom command character, push it back, weird go-to Q. If the character is not mapped, push it back, weird go-to R.
Θ	Pop a PDA, push it to the PDA stack of the parent execution environment. Errors: If the PDA stack is empty, weird-goto Q. If there is no parent execution environment, push everything already popped back, weird-goto R.
θ	Pop a PDA from the PDA stack of the parent execution environment, push it to this execution environment. Errors: If the parent's PDA stack is empty, weird-goto Q. If there is no parent execution environment, weird-goto R.
ψ	Pop a string, execute it in the execution environment of the top PDA. Errors: If the PDA stack is empty, push everything already popped back, weird-goto Q. If an invalid string element was encountered while popping B, push everything already popped back, weird-goto R. If the top PDA has no execution environment, push everything already popped back, weird-goto S.
Ψ	Pop a string, execute it in the parent execution environment. Errors: If there is no parent execution environment, push everything already popped back, weird-goto Q. If an invalid string element was encountered while popping B, push everything already popped back, weird-goto R.

Computational class

This is a strict superset of PDAsephone, and PDAsephone is Turing-complete by simulation of Brainfuck minus - (though both PDAsephone and PDAsephtwo can be used much more efficiently outside the proof construction), so PDAsephtwo is Turing-complete.