Beyond NAND

Question 1

How can we count NAND++ programs?

Answer 1

We can convert programs to their binary representations

Question 2

How does a NAND++ interpreter work? How is it different from a NAND interpreter?

Answer 2

The function NANDinterpreter takes in a program and all a table of the values of its variables, and runs the NAND program to update this table. Can return the evaluation of program on any input of the fixed length.

The function NANDPPinterpreter takes in a NAND++ program P and an input x. It initializes a table corresponding to the input, and then continuously feeds the program P to the NAND interpreter (replacing in iteration k the value of i with index(k)).

First, the interpreter sets up a variable array for the given length (set up x and validx). Then, for every loop iteration k, the interpreter sets up a NAND program by replacing instances of i with index(k) in the NAND++. The interpreter then passes the program and the variable array to the NAND interpreter for evaluation. The interpreter keeps doing this until loop == 0.

for reference: https://nbviewer.jupyter.org/gist/boazbk/7f9d42c736bee9c1cf9f2e40db1a8ccd