min_infmachine

MIN INF MACHINE:

MinInfMachine - Minimalistic infinite machine with reduced interface. It is infinite machine with random access memory.

Basics description.

MinInfMachine is extended infinite machine (like Turing machine) with random access memory. The machine model contains memory address memory, temporary buffer (temp buffer) memory, main memory, memory address position, temp buffer position, internal state and function return. Memory address and temp buffer are memory with sequential access. Temp buffer is only name doesn't mean that memory is temporary. Main memory is memory with random access. Memory address position and temp buffer position are position of corresponding memories. Internal state and function return points to transition table entry. Function return (func_ret) returnd value by previous instruction in previous cycle.

All memories contains bits and bits are cell of that memories. Position in sequential memory points to cell of that memory and memory address points to bit of main memory. Default initial value of any element of machine is zero.

MinInfMachine transition table contains main entries that are pair of two entries. First entry for func_ret=0 and second for func_ret=1. Entry contains next internal state and function (instruction) to execute. In this implementation transition table divided into two parts: entries for func_ret=0 and entries for func_ret=1. Index is internal state and number of possible internal states should be power of two.

MinInfMachine works in following cycle:

1. Load next internal state and function from transtion table using internal state and function return.
2. Store next internal state to current internal state.
3. Execute function (instruction).
4. Store result from function (instruction) to function return.

Details

Terms:

• memory - main memory of machine.
• mem_address - memory address that used to address memory. It infinite sequential memory.
• temp_buffer - extra infinite sequential memory.
• machine function - in other words it is machine instruction. It make in current step.
• func_return - func_ret - function (instruction) return that returned by previous step.

rev_mem_address - reverse memory addressing: it doesn't change behaviour of machine. It changes organization of main memory in real computer memory (it reverses memory address bits).

Main memory contains 1-bit cells and addressed by flat model. Memory is infinite. Memory address is infinite. Temp buffer is temporary buffer that simplify operations on memory address avoiding conflicts while replaced memory address by other. Temp buffer is infinite. Machine interface:

• Input: [STATE, FUNC_RETURN]

• Output: [STATE, FUNC]

• STATE - internal state.

• FUNC_RETURN - 1-bit returned value by function (func_ret). Initial value is zero.

• FUNC - 4-bit. Function (instruction) - it is opcode of function (instruction).

Implemented functions (instructions)

List of implemented functions (instructions) in form: opcode - description.

Memory operations:

• 1 - memory read. Reads main memory cell from current memory address.
• 2 and 3 - memory read and write. Reads cell from main memory and write 0 or 1 to cell from main memory. Reads and write to main memory cell in current memory address. If opcode is 2 then write 0 to memory cell, otherwise write 1.
• 5 - memory address read. Reads memory address cell from current memory address position.
• 6 and 7 - memory address read and write. Reads cell from memory address and write 0 or 1 to cell from memory address. Reads and write to memory address cell in current memory address position. If opcode is 6 then write 0 to memory cell, otherwise write 1.
• 9 - temp buffer read. Read temp buffer cell from current temp buffer position.
• 10 and 11 - temp buffer read and write. Reads cell from temp buffer and write 0 or 1 to cell from temp buffer. Reads and write to temp buffer cell in current temp buffer position. If opcode is 10 then write 0 to memory cell, otherwise write 1.

Memory operations returns value of read cell.

Movements:

• 0 - move forward position of memory address. Returns read memory address cell from previous position.
• 4 - move backward position of memory address. Returns 1 if movement done, otherwise returns 0.
• 8 - move forward position of temp buffer. Returns read temp buffer cell from previous position.
• 12 - move backward position of temp buffer. Returns 1 if movement done, otherwise returns 0.

Movement functions returns 1 if movement done, otherwise returns 0.

Special function:

• 13, 14, 15 - stop machine.