mellonis / post-machine-js Goto Github PK

View Code? Open in Web Editor NEW

0.0 2.0 0.0 2.09 MB

🧘🏼‍♂️ A convenient Post-Turing machine (based on @turing-machine-js/machine)

License: GNU General Public License v3.0

JavaScript 100.00%

simulator post-machine post-machine-simulator turing-machine

post-machine-js's Introduction

post-machine-js

A convenient Post machine.

Under the hood, the PostMachine class builds some States for TuringMachine from provided instructions. When you run it, it runs the built TuringMachine.

This repository contains following packages:

@post-machine-js/machine

An example

A tape contains two marked sections divided by the blank symbol(s). The issue is to move the first section close to the second. In other words, to remove blank symbols between these sections.

This example demonstrates an issue solving.

import PostMachine, {
  check, erase, left, mark, right, stop, Tape,
} from '@post-machine-js/machine';

const machine = new PostMachine({
  10: erase,
  20: right,
  30: check(20, 40),
  40: mark,
  50: right,
  60: check(70, 90),
  70: left,
  80: stop,
  90: left,
  100: check(90, 110),
  110: right(10),
});

machine.replaceTapeWith(new Tape({
  alphabet: machine.tape.alphabet,
  symbolList: ['*', '*', '*', ' ', ' ', ' ', '*'],
}));

console.log(machine.tape.symbolList.join('').trim()); // ***   *

machine.run();

console.log(machine.tape.symbolList.join('').trim()); // ****

An example with subroutines

A tape contains a marked section. The issue is to duplicate it.

This example demonstrates an issue solving with subroutines. A subroutine is a peace of code which can be reused multiple times. The issue could be solved without subroutines at all, but with them the algorithm looks more readable.

import PostMachine, {
  call, check, erase, left, mark, right, stop, Tape,
} from '@post-machine-js/machine';

const machine = new PostMachine({
  leftAndGoToBlank: {
    1: left,
    2: check(1, 3),
    3: stop,
  },
  rightAndGoToBlank: {
    1: right,
    2: check(1, 3),
    3: stop,
  },
  markTwoCells: {
    1: [mark, right, mark],
  },
  1: call('leftAndGoToBlank'),
  2: [right, erase],
  3: call('rightAndGoToBlank'),
  4: call('rightAndGoToBlank'),
  5: call('markTwoCells'),
  6: call('leftAndGoToBlank'),
  7: left,
  8: check(1, 9),
  9: stop,
});

// the first run

machine.replaceTapeWith(new Tape({
  alphabet: machine.tape.alphabet,
  symbolList: ['*'],
}));

console.log(machine.tape.symbolList.join('').trim()); // *

machine.run();

console.log(machine.tape.symbolList.join('').trim()); // **

// the second run

machine.replaceTapeWith(new Tape({
  alphabet: machine.tape.alphabet,
  symbolList: ['*', '*', '*'],
}));

console.log(machine.tape.symbolList.join('').trim()); // ***

machine.run();

console.log(machine.tape.symbolList.join('').trim()); // ******

post-machine-js's People

Contributors

Watchers

post-machine-js's Issues

Check links to the @turing-machine-js library from the README.md files

Improve documentation

Sub-subroutines and ability to call routines from the upper scope

A concept

There is an opportunity to define subroutines, but a defined subroutine cannot define its own subroutines. This ability must be implemented.

Subroutines from the upper scope named the same as subroutines in local scope must be overrode.

An example

const machine = new PostMachine({
  sr1: {
    sr1: {
      10: erase,
    },
    10: call('sr2'),
    20: call('sr1'),
  },
  sr2: {
    10: mark,
  },
  10: call('sr1'),
});

machine.run();

Command list in one instruction

A concept

The PostMachine constructor requires each instruction to have its own index. Sometimes this is not necessary. If a declared command in instruction does not receive the next instruction index, the machine executes the command that follows the current one.

It would be great if there will be a mechanism to group commands and assign only one index to that group.

An example

const machine = new PostMachine({
  10: [
    mark,
    right,
    mark,
    right,
    mark,
    right, 
  ],
});

machine.run();

Subroutines and the noop instruction

A concept

An algorithm is represented by the initial state and some terminal states. The machine stops when it reaches a terminal state. @turing-machine-js/machine gives ability to run subroutines whose implemented by State class instance by override terminal states.

Provided to the PostMachine constructor instructions can be indexed by integer keys. Not integer keys are forbidden now. So these keys can be used as entry points to subroutines.

Need to implement the call instruction which will execute named subroutine.

Also, noop instruction cold be useful and can be implemented in this issue.

An example

import PostMachine, { left, right, check, erase, stop, Tape } from '@post-machine-js/machine';

const machine = new PostMachine({
  ToBegin: {
    10: left,
    20: check(10, 30),
    30: right,
  },
  ToEnd: {
    10: right,
    20: check(10, 30),
    30: left,
  },
  PreviousSection: {
    10: left,
    20: check(30, 10),
    30: stop,
  },
  NextSection: {
    10: right,
    20: check(30, 10),
    30: stop,
  },
  10: noop(30),                // noop/noop(ix) - a new command which does nothing
                               // it helps to implement a pure goto operation
                               // also can be used as a place for future instructions
  20: call('NextSection', 40), // call(name)/call(name,ix) - a new command which executes a subroutine by name
                               // after executing a subroutine the machine executes the next instruction
                               // or ix'th if ix was provided
  30: call('ToEnd', 20),
  40: call('ToEnd'),
  50: erase,
});

machine.tape = new Tape({
  alphabet: machine.tape.alphabet,
  symbolList: ['*', '*', '*', ' ', ' ', '*', '*'],
  viewportWidth: 13,
});

console.log(machine.tape.viewport); // ***  **

machine.run();

console.log(machine.tape.viewport); // ***  *

mellonis / post-machine-js Goto Github PK

post-machine-js's Introduction

post-machine-js

An example

An example with subroutines

post-machine-js's People

Contributors

Watchers

post-machine-js's Issues

A concept

An example

A concept

An example

A concept

An example

Recommend Projects

Recommend Topics

Recommend Org