Register Machine

Register Machines are a computational model useful to make proofs about computational theories. They are very useful in theory of Computer Science. A similar model are the Turing Machines. The definition of the Register Machines can be found in these lecture notes, section 1.2 (in portuguese). It is built in C++.

Source Code

Usage

Extract the source code into your project.
Include the file regmachine.h and add the file regmachine.cpp to your files to compile.
Compile with g++ or with Visual Studio.
You can use make examples to build the examples.

Language

This language is an extension to the C++ language. As such, before compiling, the programs are translated into C++ code and compiled as so. All features of C++ are still valid and can be used, but since Register Machines are a computational model usually this is not useful.

The examples bellow should be self explanatory about the instructions allowed.

Examples

Decide AlphaPar (file dec-AlphaPar.cpp):

#include "regmachine.h"

Register R0("aaa");

INIT_REGMACHINE("a")

L0 IF R0=E THEN L6 ELSE L1;
L1 LET R0=R0-a;
L2 IF R0=E THEN L5 ELSE L3;
L3 LET R0=R0-a;
L4 IF R0=E THEN L6 ELSE L1;
L5 LET R0=R0+a;
L6 PRINT;
L7 HALT;

END_REGMACHINE

Enumerate AnBn (file enum-AnBn.cpp):

#include "regmachine.h"

Register R0;
Register R1;

INIT_REGMACHINE("ab")

L0 PRINT;
L1 IF R0=E THEN L5 ELSE L5 OR L2;
L2 LET R0=R0-b;
L3 LET R1=R1+b;
L4 IF R0=E THEN L5 ELSE L5 OR L2;
L5 LET R0=R0+a;
L6 LET R0=R0+b;
L7 IF R1=E THEN L11 ELSE L7 OR L8;
L8 LET R1=R1-b;
L9 LET R0=R0+b;
L10 IF R1=E THEN L11 ELSE L7 OR L8;
L11 PRINT;

PAUSE

L12 IF R0=E THEN L1 ELSE L1 OR L1;
L13 HALT;


END_REGMACHINE