Z-complete

Z-complete is a concept proposed by PSTF.

Because I accidentally lost a software that generates strange text, making it difficult to input Fraktur script, the title here should actually be Z-complete.

Requirements

A programming language is supposed to be Z-complete if they can:

1. Determine whether an expression is true, for example, check whether 6 is not equal to 5.
2. Store data in any medium(including variable), such as a register.
3. Simulate a Minsky machine.
4. Recursively call a procedure.
5. Support floating point numbers or fractions.

Further Requirements

Z-complete Level 2 is also called A-complete. A programming language is supposed to be A-complete if they:

1. Be able to implement Wolfram Rule-110.
2. Have a program to simulate a Turing machine.
3. Have the pair type or the complex type.

Example of Z-complete programming language

Brainfuck

1. It can check whether current cell is not 0.
2. Data are stored in a tape.
3. See below.
4. See at Brainfuck Algorithm.
5. Yes, but it need a LOT of calculations.

> Minsky Machine in Brainfuck
> Tape layout: [0: counter1, 1: counter2, 2: program counter, 3: temp, 4: temp2]

> Initialize: set up initial program counter
+++>++>       [Set initial state: program starts at instruction 3]

> Main interpreter loop
[             While program counter != 0
  
  >>>>+<<<<   [Mark that we're executing]
  
  >           [Move to program counter]
  
  >           [Check which instruction to execute]
  
  > Instruction dispatch
  [->+>+<<]>>[-<<+>>]  [Copy program counter to temp]
  
  >           [Check for instruction 0: HALT]
  >++<        [Prepare to check if pc == 0]
  [-<->]      [Compare]
  <[          [If program counter == 0]
    -         [HALT - clear program counter]
    >>>>>-<<<<< [Clear execution flag]
  <]
  
  >           [Check for instruction 1: INC R1]
  >+<         [Prepare to check if pc == 1]
  [-<->]      [Compare]
  <[          [If program counter == 1]
    <<+       [Increment R1]
    >>+       [Increment program counter to next instruction]
    >>>>>-<<<<< [Clear execution flag]
  <]
  
  >           [Check for instruction 2: INC R2]
  >++<        [Prepare to check if pc == 2]
  [-<->]      [Compare]
  <[          [If program counter == 2]
    <+        [Move to R2]
    >+<       [Increment R2]
    >+        [Increment program counter to next instruction]
    >>>>>-<<<<< [Clear execution flag]
  <]
  
  >           [Check for instruction 3: DEC R1 (or jump if zero)]
  >+++<       [Prepare to check if pc == 3]
  [-<->]      [Compare]
  <[          [If program counter == 3]
    <<        [Move to R1]
    [->+<]    [If R1 != 0, decrement it]
    >[        [If R1 was zero, jump to instruction 5]
      >>+++   [Set program counter to instruction 5]
    <]        [Else continue to next instruction]
    [         [If R1 was non-zero]
      >>+     [Increment program counter to next instruction]
    <]
    >>>>>-<<<<< [Clear execution flag]
  <]
  
  >           [Check for instruction 4: DEC R2 (or jump if zero)]
  >++++<      [Prepare to check if pc == 4]
  [-<->]      [Compare]
  <[          [If program counter == 4]
    <         [Move to R2]
    [->+<]    [If R2 != 0, decrement it]
    >[        [If R2 was zero, jump to instruction 5]
      >>+++   [Set program counter to instruction 5]
    <]        [Else continue to next instruction]
    [         [If R2 was non-zero]
      >>+     [Increment program counter to next instruction]
    <]
    >>>>>-<<<<< [Clear execution flag]
  <]
  
  >           [Check for instruction 5: HALT]
  >+++++<     [Prepare to check if pc == 5]
  [-<->]      [Compare]
  <[          [If program counter == 5]
    -         [HALT - clear program counter]
    >>>>>-<<<<< [Clear execution flag]
  <]
  
  <<<         [Return to program counter position]
]

> Final cleanup and display (optional)
<<<.>>>.     [Output final counter values]