セミコロンレスJava はチューリング完全か？

セミコロンレスJava (Semicolonless Java)というのは Java でセミコロンを使わずにコードを書くというチャレンジである。ネタであり言語の構文を駆使して行うプログラミングパズルの類の遊びである。（ときどき本気にしてその有用性について聞いてくる人がいるので、この冗談がどういう冗談でどう面白いのかの解説のような無粋なことを書いている）

ところで、セミコロンを使わずともJavaはチューリング完全なのであろうか？

証明方法

チューリング完全であるという証明は、すでにチューリング完全であることが知られている体系を該当環境で実装することで行うのが簡単な方法論である。

Brainf*ck といったチューリング完全な簡易プログラミング言語を実装するとか、チューリング完全であることが知られているライフゲームを実装するとかが考えられる。

今回は、ライフゲームの1次元版とも言える、1次元セルオートマトンを作成することでこの証明を行う。

Elementary cellular automaton （基本セルオートマトン）は 0 と 1 の連続したセルからなり、自身とその両隣、つまり3bitの組み合わせから、次世代のセルの値が定まる。

f:id:Nagise:20200527201721g:plain — 基本セルオートマトン

この3bitの組み合わせ8種類が、それぞれ次世代に0になるか1になるかの組み合わせが2^8通り考えられ、この組み合わせを0～255の値で表し、ルール110 などと呼ぶ。

ルール110 はチューリング完全になることが知られている。

実装

Githubにも上げてあるが、コードは短いので全文を記載する。

public class ElementaryCellularAutomaton {

	public static void main(String[] args) throws Exception {
		synchronized (new ElementaryCellularAutomaton(new Rule(110), "0000000000000001", 20)) {}
	}

	/**
	 * Run Elementary cellular automaton.
	 *
	 * @param rule
	 * @param states initial states. made of "0" and "1"
	 * @param generation
	 */
	public ElementaryCellularAutomaton(Rule rule, String states, int generation) throws Exception {
		synchronized (new Output(states)){}

		while (--generation  > 0) {
			synchronized (new Output(states = new Next(states, rule).peek().toString())){}
		}
	}

	/**
	 * Calculate the next generation.
	 */
	static class Next extends java.util.Stack {
		/**
		 * Calculate the next generation.
		 * @param states
		 * @param rule
		 * @return String : next generation
		 */
		public Next(String states, Rule rule) {
			synchronized(push(new Next(states, (char[])rule.peek(), 0, new StringBuffer()).peek())) {}
		}

		private Next(String states, char[] map, int x, StringBuffer sb) {
			synchronized (sb.append(map[(states.charAt(states.length()-1)-'0')*4
					+(states.charAt(0)-'0')*2
					+states.charAt(1)-'0'])) {}
			while (x<states.length()-2) {
				synchronized (sb.append(map[(states.charAt(x) - '0')*4
						+(states.charAt(x+1) - '0')*2
						+states.charAt(x++ +2) - '0'])) {}
			}
			synchronized (push(sb.append(map[(states.charAt(states.length()-2)-'0')*4
					+(states.charAt(states.length()-1)-'0')*2
					+states.charAt(0)-'0']))) {}
		}
	}

	/**
	 * https://en.wikipedia.org/wiki/Elementary_cellular_automaton#The_numbering_system
	 */
	static class Rule extends java.util.Stack {
		/**
		 * create Rule Object.
		 * @param ruleNo the rule number of the automaton.
		 */
		public Rule(int ruleNo) {
			synchronized(push(new Rule(110, 0, new char[8]).peek())) {}
		}

		private Rule(int ruleNo, int i, char[] map) {
			while (i<8) {
				switch (map[i++] = (char)('0' + (ruleNo & 1))) {}
				switch (ruleNo >>= 1) {}
			}
			synchronized (push(map)) {}
		}
	}

	/**
	 * System.out.println() utility
	 */
	static class Output {
		/**
		 * Output message to System.out
		 * @param message message
		 */
		public Output(String message) throws Exception {
			if (null == java.io.PrintStream.class
					.getMethod("println", new Class[] {String.class})
					.invoke(System.out, new Object[] {message})){}
		}
	}
}

動かし方

コンパイルしてmainを実行するだけ。

パラメータはハードコーディングしてしまっているので、いじりたい場合は以下の部分の値を変更してください。

synchronized (new ElementaryCellularAutomaton(new Rule(110), "0000000000000001", 20)) {}

new Rule(110) は先に解説した基本セルオートマトンのルールの値である。

"0000000000000001" は基本セルオートマトンの初期値。0と1からなる文字列で指定する。とりあえず16文字にしているが、この文字数は多くすることが可能。

20 は出力する世代数。大きな値にすればそのぶん先の世代まで出力してくれる。

技法

本コードは Java 1.1 相当のコードとなっている。一般にセミコロンレスJavaは古いJavaほど構文の制約が多く、難易度が高いとされる。Java1.0での Hello world は未解決問題となっており、Java1.1が事実上の最難関とされる。

セミコロンレスJavaの構造化の手法は過去記事セミコロンレスJavaの構造化＆オブジェクト指向 - プログラマーの脳みそが詳しい。
セミコロンレスJavaではreturn文が書けないため、戻り値のあるメソッドは定義することができない。そして、戻り値のないメソッドは呼び出しが式にできないためセミコロンなしで呼びだせない。（リフレクションを用いることで回避することができるが、記述が煩わしい）

そこで、java.util.Stackを継承したclassをnewすることでコンストラクタをメソッド呼び出しの代替とし、peek()で戻り値となる値を読みだすという手法で構造化を行う。

Java5 以降であれば、for-each構文でローカル変数宣言を行うことが可能なのだが、Java1.1ではその手法が用いれないためコンストラクタの引数を用いて変数宣言の代用としている。

結論

Java 1.1 はセミコロンを用いずともチューリング完全であることが示された。