PhD

PhD

Paradigm(s)	Imperative, Declarative
Designed by	User:Hakerh400
Appeared in	2021
Computational class	Unknown
Major implementations	Interpreter
File extension(s)	.txt

PhD (Push halt Down automaton) is a PDA with a PDA-halting oracle.

Overview

There is exactly one stack of bits. The stack is initially filled with infinitely many 0 bits.

Source code consists of instructions (all other characters are ignored). Instructions are:

• 0 - push bit 0 to the stack
• ~ - invert the top bit of the stack
• * - pop a bit, if the bit is 1, then pop another bit and output it, otherwise push the next input bit
• [...] - pop a bit from the stack and if the bit is 1 then execute ... and then execute [...] again (note: ... stands for anything)
• (...) - if ... would halt when ran on the current stack, then push 0, otherwise do nothing (note: ... cannot contain characters (, ), or *), any changes made to the stack inside ... will be reverted after executing (...)

I/O format

Input is a bit array. Before program starts, each input bit is prefixed by 1 and infinitely many zeros are appended. For example, input string 1011 becomes:

111011110000000000000...

Output remains unchanged.

Examples

Cat program

*[0*0~*0*]

Try it online

Truth-machine

*0*[0~0~*0~]~0~*

Try it online

Hello, World!

00~*00~*00~*0~0~*00~*00~*0~0~*00~*0~0~*00~*0~0~*00~*00~*0~0~*0~0~*00~*00~*00~*0~0~*0~0~*00~*0~0~*0~0
~*00~*00~*00~*0~0~*0~0~*00~*0~0~*0~0~*00~*0~0~*0~0~*0~0~*0~0~*00~*0~0~*0~0~*00~*00~*00~*0~0~*0~0~*00
~*0~0~*00~*00~*00~*00~*00~*00~*00~*0~0~*00~*00~*0~0~*0~0~*0~0~*00~*0~0~*00~*0~0~*00~*0~0~*0~0~*0~0~*
0~0~*00~*0~0~*0~0~*00~*00~*0~0~*00~*00~*0~0~*0~0~*0~0~*00~*00~*00~*0~0~*0~0~*00~*0~0~*0~0~*00~*00~*0
0~*0~0~*00~*00~*0~0~*0~0~*00~*0~0~*00~*00~*00~*00~*0~0~*

Try it online

If-then-else

If the input is 0, then output 1011, and if the input is 1 output 001

*0*[[0]00~*00~*0~0~*00][0~0~*00~*0~0~*0~0~*0]

Try it online

Computational class

Unknown.

Interpreters

Interpreter