Javagony Turing-completeness proof

From Esolang
Jump to navigation Jump to search
← Back to Javagony

This page will show the Turing-completeness of Javagony by implementing a brainfuck interpreter in it. (This was before the author realized Java had the assert statement, which would've made things a lot easier.)

The code

Main.java

  • The starting point for the program
  • Creates a new Proof and calls its doWhileValueNe0 method
class Main
{
  public static void main(String[] args)
  {
    Proof n = new Proof();
    n.tape.write(48);
    n.doWhileReadNe0(n::F1);
  }
}

Proof.java

  • Class to use the Tape class and a doWhileValueNe0 method
  • The real "meat" of the proof
class Proof
{
  public Tape tape;

  public Proof()
  {
    this.tape = new Tape();
  }
  public void doWhileReadNe0(VFuncV f)
  {
    //Loop until this.tape.read()==0
    int[] a = new int[1];
    try
    {
      System.out.print(a[this.tape.read()] + "\r");
    }
    catch(IndexOutOfBoundsException e)
    {
      f.vfuncv();
      this.doWhileReadNe0(f);
    }
  }

  public void F1()
  {
    System.out.println("Tape: " + this.tape.read());
    this.tape.write(this.tape.read() - 1);
  }
}

Tape.java

  • Class to simulate brainfuck's tape
  • Bounded cells, but unbounded length
import java.util.List;
import java.util.ArrayList;

class Tape
{
  private List<Integer> tape;
  private int head;

  public Tape()
  {
    this.tape = new ArrayList<Integer>();
    this.tape.add(0);
    this.head = 0;
  }
  public void left()
  {
    this.head -= 1;
  }
  public void right()
  {
    this.head += 1;
    try
    {
      System.out.print(this.tape.get(this.head) + "\r");
    }
    catch(IndexOutOfBoundsException e)
    {
      this.tape.add(0);
    }
  }
  public void write(Integer i)
  {
    this.tape.set(this.head, i);
  }
  public int read()
  {
    return this.tape.get(this.head);
  }
}

VFuncV.java

  • SAM type that takes no arguments and returns no value
  • Used in the Proof class's doWhileReadNe0 method to simulate a while loop
interface VFuncV
{
  void vfuncv();
}

The proof

See here for a brainfuck intepreter

VFuncV.java contains an SAM type, VFuncV, that takes no arguments and returns no value. The Proof class's doWhileReadNe0 method takes a VFuncV as a parameter and repeatedly evaluates it until its tape's read() method returns 0; this is in effect a while loop. The way this and the tape are implemented, as well as the way it's called with the Proof class's F1 method, should make Turing-completeness clear. For every [while loop] in a brainfuck program, add a new method to the Proof class, and make that method call the doWhileReadNe0 method again if brackets are nested.

Brainfuck Javagony
+ tape.write(tape.read() + 1);
- tape.write(tape.read() - 1);
< tape.left();
> tape.right();
[ Add a new method to the Proof class
] Add a new method to the Proof class

IO is unnecessary (integers followed by \r (carriage return, to blank them out) are constantly being printed, so it would be difficult anyways without changing the method).

And now for a brainfuck interpreter...

This interprets a version of brainfuck with no IO and changed commands as follows:

Brainfuck Brainfuck::Javagony
+ (
- )
> *
< +
[ ,
] -

The interpreter is the interpret method of the Proof class. Main.java takes one command-line argument, the code to run.

Main.java

class Main
{
  public static void main(String[] args)
  {
    try
    {
      Proof p = new Proof();
      String program = args[0];
      p.interpret(program);
    }
    catch(IndexOutOfBoundsException e)
    {
      System.out.println("Usage: Main.java code");
    }
  }
}

Proof.java

import java.util.Stack; import java.util.Map; import java.util.HashMap;
class Proof
{
  public Tape tape;
  public int i; //for repeatNTimes
  public String codestr; //for matchBrackets
  public int codeIndex;
  public Stack<Integer> brktmp;
  public Map<Integer, Integer> brkmap;
  public Proof()
  {
    this.tape = new Tape();
    this.brktmp = new Stack<Integer>();
    this.brkmap = new HashMap<Integer, Integer>();
  }
  public void doWhileReadNe0(IVFuncV f)
  {
    int[] a = new int[1];
    try
    {
      System.out.print(a[this.tape.read()] + "\r");
    }
    catch(IndexOutOfBoundsException e)
    {
      f.vfuncv();
      this.doWhileReadNe0(f);
    }
  }
  public void repeatNTimes(IVFuncV f, int n)
  {
    this.i = 0;
    this.repeatNTimesPri(f, n);
  }
  private void repeatNTimesPri(IVFuncV f, int n)
  {
    int[] a = new int[n];
    try
    {
      System.out.print(a[this.i] + "\r");
      f.vfuncv();
      ++this.i;
      this.repeatNTimesPri(f, n);
    }
    catch(IndexOutOfBoundsException e)
    {}
  }

  public void interpret(String code)
  {
    this.codestr = code;
    this.matchBrackets();
    this.codeIndex = 0;
    this.interpretPri();
  }
  private void interpretPri()
  {
    try
    {
      System.out.print(this.codestr.charAt(this.codeIndex) + "\r");
      this.execOneCharacter();
      this.interpretPri();
    }
    catch(StringIndexOutOfBoundsException e)
    {}
  }

  public void matchBrackets()
  {
    this.repeatNTimes(this::matchBracketsIter, this.codestr.length());
  }
  public void matchBracketsIter()
  {
    int c = (int) this.codestr.charAt(this.i);
    int[] a = new int[1];
    try
    {
      System.out.print(a[44 - c] + "\r");
      //Handle [
      this.brktmp.push(this.i);
    }
    catch(IndexOutOfBoundsException e1)
    {
      try
      {
        System.out.print(a[45 - c] + "\r");
        //Handle ]
        int n = this.brktmp.pop();
        this.brkmap.put(n, this.i);
        this.brkmap.put(this.i, n);
      }
      catch(IndexOutOfBoundsException e2)
      {}
    }
  }

  private void execOneCharacter()
  {
    int c = (int) this.codestr.charAt(this.codeIndex) - 40; //0..5
    int[] a = new int[1];
    try
    {
      System.out.print(a[5 - c] + "\r");
      //Handle ]
      this.codeIndex = this.brkmap.get(this.codeIndex) - 1;
    }
    catch(IndexOutOfBoundsException e1)
    {
      try
      {
        System.out.print(a[4 - c] + "\r");
        //Handle [
        try
        {
          System.out.print(a[this.tape.read()]);
          this.codeIndex = this.brkmap.get(this.codeIndex);
        }
        catch(IndexOutOfBoundsException e1a)
        {}
      }
      catch(IndexOutOfBoundsException e2)
      {
        try
        {
          System.out.print(a[3 - c] + "\r");
          //Handle <
          this.tape.left();
        }
        catch(IndexOutOfBoundsException e3)
        {
          try
          {
            System.out.print(a[2 - c] + "\r");
            //Handle >
            this.tape.right();
          }
          catch(IndexOutOfBoundsException e4)
          {
            try
            {
              System.out.print(a[1 - c] + "\r");
              //Handle -
              this.tape.write(this.tape.read() - 1);
            }
            catch(IndexOutOfBoundsException e5)
            {
              //Handle +
              this.tape.write(this.tape.read() + 1);
            }
          }
        }
      }
    }
    ++this.codeIndex;
  }
}

Tape.java

import java.util.List;
import java.util.ArrayList;

class Tape
{
  private List<Integer> tape;
  private int head;

  public Tape()
  {
    this.tape = new ArrayList<Integer>();
    this.tape.add(0);
    this.head = 0;
  }
  public void left()
  {
    this.head -= 1;
  }
  public void right()
  {
    this.head += 1;
    try
    {
      System.out.print(this.tape.get(this.head) + "\r");
    }
    catch(IndexOutOfBoundsException e)
    {
      this.tape.add(0);
    }
  }
  public void write(Integer i)
  {
    this.tape.set(this.head, i);
  }
  public int read()
  {
    return this.tape.get(this.head);
  }
}

IVFuncV.java

interface IVFuncV
{
  void vfuncv();
}
Retrieved from "https://esolangs.org/w/index.php?title=Javagony_Turing-completeness_proof&oldid=79478"