なんか考えてることとか

変な人が主にプログラミング関連で考えていることをまとめる。

プログラミング言語であることの簡単な証明方法

プログラミング
  • 2021/08/12
    • Brainf*ckインタプリタのコードにミスを見つけたので修正
    • Brainf*ckはスタック指向ではないため「Brainf*ckはスタック指向である」旨の記述を削除

※注意※
今回の記事は人によって考えが異なる可能性のある内容が含まれています！
したがって今回の記事はあなたの納得できる内容であるとは限らないことを前もって言っておきます。

「これはプログラミング言語である」「あれはプログラミング言語ではない」・・・
プログラミング言語であるか否か、結構様々な意見が飛び交うことのあるプログラミング業界。しかし、その判断基準は非常に曖昧であることがほとんどである。
今回は、プログラミング言語における自分なりの明確な判断基準について書いていこうと思う。

プログラミング言語の定義について

プログラミング言語の定義をするために、そもそもプログラミングについて定義する必要があるだろう。
自分の中でのプログラミングの定義は、

問題を解決するために、プログラムを書くこと

である。
この問題というのは、たとえば「512+128は？」といった単純なものから「これを作ってみたい、そのためにはどうればいいのか？」といった個人的なもの、「人々がこの理由で困っている、それを解決するには？」といった世の中に役立つためのものなど様々である。

そしてそのプログラムを書くうえで必要となるのが、プログラミング言語である。

様々な問題を解決するためには、当然ながら様々な問題を解決する能力が必要だろう。
それはすなわち、「プログラミング言語である」とは、「そのプログラミング言語を使って様々な問題を解決できる」ことを示していると言える。

では「様々な問題を解決できる」ことを証明するためには？自分はそれを証明する簡単な方法として「チューリング完全性が高い*1」ことを証明する方法を書いていきたいと思う。

「チューリング完全性が高い」とは？

そもそもチューリング完全性とは？それを知るためには、万能チューリングマシンについて知る必要があるし、それを理解するためにさらにチューリングマシンも理解する必要がある。

では順に解説していく。

チューリングマシン

まずチューリングマシンについてまで詳細に解説していくと、複雑になってしまうため省くこととする。
チューリングマシンについて簡単に説明すると、

あらかじめ機能と状態を持った表をもとに、テープを読み書きする仮想的な計算機

である。
ここで重要なのが「あらかじめ機能と状態を持った表をもとに」というところで、お察しのとおり、1つのチューリングマシンが様々な問題を解く能力を持つわけではない。つまり、チューリングマシンを再現できるというだけでは、「チューリング完全性が高い」ことを示すことはできないわけである。

万能チューリングマシン

では、チューリングマシンを模倣できるチューリングマシンがあったらどうだろうか？

たとえば問題xを解くことのできるチューリングマシンX、問題yを解くことのできるチューリングマシンYがあったとする。
チューリングマシンXは問題xを解くのに適しているため、問題xを解くことができ、チューリングマシンYは問題yを解くのに適しているため、問題yを解くことができる。

f:id:opaupafz2:20210808122618p:plain

しかし、チューリングマシンXは問題yを解くのに適しておらず、問題yを解くことはできない。チューリングマシンYも同様に問題xを解くのに適していないため、問題xを解くことができない。

f:id:opaupafz2:20210808123339p:plain

そこで、チューリングマシンXとチューリングマシンYを模倣するチューリングマシンZを作る。

f:id:opaupafz2:20210808123813p:plain

こうすることで、チューリングマシンZはチューリングマシンXとチューリングマシンYを模倣できるため、問題xも問題yも解くことができる。

f:id:opaupafz2:20210808124255p:plain

このように、様々なチューリングマシンを模倣できるようにし、様々な問題の解決に対応したチューリングマシンを万能チューリングマシンと呼ぶ。

チューリング完全性

そしてチューリング完全性とは、「万能チューリングマシンと同等の能力を持つか」を示すものである。
万能チューリングマシンとほぼ同等*2の能力を持つことを、「チューリング完全性が高い」と言う。

「チューリング完全性が高い」ことの証明方法

ここまでで、「プログラミング言語である」ことを簡単に証明するためには、「様々な問題を解決できる能力を持つ」ことを証明する必要があり、その簡単な証明方法として「チューリング完全性が高い」ことを示せば良いことがわかった。

では、「チューリング完全性が高い」ことを示すにはどうすれば良いのか？これも簡単に証明できる方法がある。
それは、「チューリング完全性が高いと証明されているものを模倣する」ことである。以下に、その例とともにコードを紹介していこうと思う。

その前にあらかじめ言っておくと、今回のコードは「チューリング完全性が高い」ことを示すためのコードなので、例外処理は入れていないことをご理解いただきたい。（文字数これ以上増やしたくないからと言うのは内緒）

Rule110 in C

Rule110は「チューリング完全性が高い」と言うことが証明されている。そのため、Rule110を実装できることは「チューリング完全性が高い」ことを示しているのと同義である。
これをCで実装してみる。

  • Rule110のルール

Rule110は複数のセルからなるオートマトンである。以下のルールセットによりそのルールは構成されている。

上段セルのパターン 111 110 101 100 011 010 001 000
下段中心セルの状態 0 1 1 0 1 1 1 0

まず最初に起点となるセルを決めておいて、あとは上段から順番にパターンを読んでいって下段の中心のセルを決定させていき、その段が終わったら下段のパターンを読んでいく・・・を繰り返す単純なものとなっている。

今回Cで実装する際に、以下の条件を設ける。

  1. C99以降の可変長配列を用いる
  2. 視覚性、簡単のために標準Cライブラリを用いる
  3. セルのサイズ、起点となるセルの座標はコマンドライン引数により指定する
    => その際、起点となるセルの座標は1つだけとする
  4. 左右に折り返す仕様であるとする*3

ではRule110を実装したCコードを以下に示す（GCC環境とする）。

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define EPOCH_X atoi(argv[3])-1 /* 起点x軸 */
#define EPOCH_Y atoi(argv[4])-1 /* 起点y軸 */
#define X_MAX   pos_max[0]+1    /* x軸最大 */
#define Y_MAX   pos_max[1]      /* y軸最大 */

/**
 * Rule110のルールセット
 */
static char rule110_pattern[8][3] = {
    "***",
    "** ",
    "* *",
    "*  ",
    " **",
    " * ",
    "  *",
    "   "
};
static char rule110_detect[8] = {
    ' ',
    '*',
    '*',
    ' ',
    '*',
    '*',
    '*',
    ' '
};

/* プロトタイプ宣言 */
void cell_init(int x_max, int y_max, char[y_max][x_max]);
void rule110_start(int x_max, int y_max, char[y_max][x_max]);
void print_cell(int x_max, int y_max, char[y_max][x_max]);

/**
 * main関数
 */
int main(int argc, char *argv[])
{
    int pos_max[2] = { atoi(argv[1]), atoi(argv[2]) };
    char cell[Y_MAX][X_MAX+1];
    
    /* セルの初期化 */
    cell_init(X_MAX, Y_MAX, cell);
    
    /* 起点となるセルの決定 */
    cell[EPOCH_Y][EPOCH_X] = '*';
    
    /* Rule110スタート */
    rule110_start(X_MAX, Y_MAX, cell);
    
    return 0;
}

/**
 * セルの初期化をする関数
 */
void cell_init(int x_max, int y_max, char cell[y_max][x_max])
{
    int i;
    int x_limit = x_max-1;
    
    for (i = 0; i < y_max; ++i) {
        memset(cell[i], ' ', x_limit);
        cell[i][x_limit] = '\0';
    }
}

/**
 * Rule110スタート関数
 */
void rule110_start(int x_max, int y_max, char cell[y_max][x_max])
{
    int i, j, k;
    int x_limit = x_max-2;
    int y_limit = y_max-1;
    int x_semifinal = x_limit-1;
    
    /* 最初のセルを表示 */
    print_cell(x_max, y_max, cell);
    
    for (i = 0; i < y_limit; ++i) {
        /* 開始と終了のパターンを作成 */
        char start_pattern[3] = {
            cell[i][x_limit],
            cell[i][0],
            cell[i][1]
        };
        char end_pattern[3] = {
            cell[i][x_semifinal],
            cell[i][x_limit],
            cell[i][0]
        };

        /* 最初のパターン */
        for (k = 0; k < 8; ++k) {
            /* 最初のパターンから下段のセルを決定させる */
            if (strncmp(start_pattern, rule110_pattern[k], 3) == 0) {
                cell[i+1][0] = rule110_detect[k];
                break;
            }
        }

        /* 途中のパターン */
        for (j = 0; j < x_limit; ++j) {
            for (k = 0; k < 8; ++k) {
                /* パターンから下段のセルを決定させる */
                if (strncmp(&cell[i][j], rule110_pattern[k], 3) == 0) {
                    cell[i+1][j+1] = rule110_detect[k];
                    break;
                }
            }
        }

        /* 最後のパターン */
        for (k = 0; k < 8; ++k) {
            /* 最後のパターンから下段のセルを決定させる */
            if (strncmp(end_pattern, rule110_pattern[k], 3) == 0) {
                cell[i+1][x_limit] = rule110_detect[k];
                break;
            }
        }
        
        /* 途中/最後のセルを表示 */
        print_cell(x_max, y_max, cell);
    }
}

/**
 * セルを標準出力で表示する関数
 */
void print_cell(int x_max, int y_max, char cell[y_max][x_max])
{
    int i;
    int x_limit = x_max-1;
    
    /* 画面の初期化 */
#ifdef _WIN32
    system("cls");
#else
    system("clear");
#endif
    
    /* 枠の上 */
    printf("+");
    for (i = 0; i < x_limit; ++i) {
        printf("-");
    }
    printf("+\n");
    
    /* セルの中身 */
    for (i = 0; i < y_max; ++i) {
        printf("|%s|\n", cell[i]);
    }
    
    /* 枠の下 */
    printf("+");
    for (i = 0; i < x_limit; ++i) {
        printf("-");
    }
    printf("+\n");
    
    /* この表示が見れるようにwaitをかける */
    sleep(1);
}

動作は以下のようになる。
f:id:opaupafz2:20210809144423g:plain

ライフゲーム in Excel VBA

ライフゲームも「チューリング完全性が高い」ことが証明されているので、これを実装できる言語は「チューリング完全性が高い」ことになる。
これをExcel VBAで実装してみる。

ライフゲームは計算機上で生命の誕生・死をシミュレーションするゲームである。セルXの周辺に生きたセルがどれぐらいいるかによって以下のように状態が変わるようになっている。

  1. 過疎・・・セルXに隣接する生きたセルが1個以下だった場合セルXの状態は「死」に変わる
  2. 維持・・・セルXに隣接する生きたセルが2個だった場合セルXの状態は変わらない
  3. 誕生・・・セルXに隣接する生きたセルが3個だった場合セルXの状態は「生」に変わる
  4. 過密・・・セルXに隣接する生きたセルが4個以上だった場合セルXの状態は「死」に変わる

その例を表に示す。

過疎維持誕生過密
セルの例 ■■■
X■XX■X■
■■■■

今回Excel VBAで実装する際に、以下の条件を設ける。

  1. 24x24とする
  2. 周りの生きたセルを数える際、折り返しを考慮しない

ではライフゲームを実装したExcel VBAコードを以下に示す。

  • Workbook
Option Explicit

'----------------------
'開いたときに初期化する
'----------------------
Private Sub Workbook_Open()
    started = False
    
    With Sheets("Sheet1")
        .Range("B:Y").ColumnWidth = 2
        .Range("B2:Y25").Interior.ColorIndex = 0
        .Range("B2:Y25").Borders.LineStyle = xlContinuous
    End With
End Sub
  • Worksheet
Option Explicit

'------------------------------
'セルを手動で「生」に変化させる
'------------------------------
Private Sub Worksheet_SelectionChange(ByVal Target As Range)
    If Target.Count > 1 Then End
    
    If Not Intersect(Target, Range("B2:Y25")) Is Nothing Then
        If Not Target.Interior.ColorIndex = 4 Then
            Target.Interior.ColorIndex = 4
        Else
            Target.Interior.ColorIndex = 0
        End If
    End If
    
    Application.EnableEvents = False
    Range("A1").Select
    Application.EnableEvents = True
End Sub
  • 標準モジュール
Option Explicit

Public started As Boolean   '開始フラグ

'----------------
'ライフゲーム本体
'----------------
Sub StartLifeGame()
    Dim result(2 To 25, 2 To 25) As Long
    Dim sheet As Worksheet
    Set sheet = Sheets("Sheet1")
    
    Do
        Application.ScreenUpdating = False
        Erase result
        CalcGen sheet, result   '次世代を計算する
        StepGen sheet, result   '次世代に移行する
        Application.ScreenUpdating = True
        DoEvents
    Loop Until started = False
End Sub

'----------------
'次世代を計算する
'----------------
Sub CalcGen(ByVal sheet As Worksheet, ByRef result() As Long)
    Dim i As Long
    Dim j As Long
    Dim k As Long
    Dim l As Long
    
    For i = 2 To 25
        For j = 2 To 25
            For k = (i - 1) To (i + 1)
                For l = (j - 1) To (j + 1)
                    If Not (k = i And l = j) Then
                        If sheet.Cells(k, l).Interior.ColorIndex = 4 Then
                            result(i, j) = result(i, j) + 1
                        End If
                    End If
                Next l
            Next k
        Next j
    Next i
End Sub

'----------------
'次世代に移行する
'----------------
Sub StepGen(ByVal sheet As Worksheet, ByRef result() As Long)
    Dim i As Long
    Dim j As Long
    
    For i = 2 To 25
        For j = 2 To 25
            Select Case result(i, j)
                Case 2
                    '特に変化なし
                Case 3
                    'セルが「生」に変化
                    sheet.Cells(i, j).Interior.ColorIndex = 4
                Case Else
                    'セルが「死」に変化
                    sheet.Cells(i, j).Interior.ColorIndex = 0
            End Select
        Next j
    Next i
End Sub

'-----------------------------------
'Startボタン: ライフゲームを開始する
'-----------------------------------
Sub Start_Click()
    If started = False Then
        started = True
        Call StartLifeGame
    End If
End Sub

'----------------------------------
'Stopボタン: ライフゲームを停止する
'----------------------------------
Sub Stop_Click()
    If started = True Then
        started = False
    End If
End Sub

'-------------------------------------------
'Clearボタン: セルをすべて「死」に初期化する
'-------------------------------------------
Sub Clear_Click()
    With Sheets("Sheet1")
        .Range("B2:Y25").Interior.ColorIndex = 0
    End With
End Sub

動作は以下のようになる。
f:id:opaupafz2:20210812104112g:plain

Brainf*ckインタプリタ in Python

Brainf*ckとは、「難解」と言われているプログラミング言語である。すべての命令が1文字の記号で表されており、読めない人には読めない。このようなプログラミング言語を「難解プログラミング言語」と言う。
「難解プログラミング言語」とは呼ばれているものの、その言語仕様自体は単純明快であり、また、インタプリタは非常に実装しやすいと言われている。
余談だが、f*ckの部分は伏せている。これが何を表すのかについては、察してほしい。
これをPythonで実装してみる。

  • Brainf*ckの言語仕様

Brainf*ckの言語仕様は以下のとおりである。

命令 意味
> ポインタをインクリメントする
< ポインタをデクリメントする
+ ポインタの指し示す値をインクリメントする
- ポインタの指し示す値をデクリメントする
. ポインタの指し示す値を標準出力する
, ポインタの指し示す値に標準入力する
[ ポインタの指し示す値が0であれば]にジャンプする
] ポインタの指し示す値が0でなければ[にジャンプする

これら以外の命令はすべて無視される。

今回Pythonで実装する際に、以下の条件を設ける。

  1. 環境はWindows環境とする
    => LinuxやMacOSでコーディングする際は一工夫必要である点に注意
  2. 入力はAsciiコード、出力はUTF-8とする。

ではBrainf*ckインタプリタを実装したPythonコードを以下に示す。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import msvcrt

def brainf_ck(cmd):
    '''
    Brainf*ckインタプリタ
    '''
    CMD_END = len(cmd)-1
    stack = [0]

    cmd_current = 0
    stack_current = 0
    while True:
        if cmd[cmd_current] == '>':
            # ポインタのインクリメント
            if (stack_current+1) == len(stack):
                stack.append(0)
            stack_current += 1
        elif cmd[cmd_current] == '<':
            # ポインタのデクリメント
            if (stack_current-1) < 0:
                stack.insert(stack_current, 0)
            else:
                stack_current -= 1
        elif cmd[cmd_current] == '+':
            # ポインタの指し示す値のインクリメント
            stack[stack_current] += 1
        elif cmd[cmd_current] == '-':
            # ポインタの指し示す値のデクリメント
            stack[stack_current] -= 1
        elif cmd[cmd_current] == '.':
            # ポインタの指し示す値の標準出力
            print(chr(stack[stack_current]), end='', flush=True)
        elif cmd[cmd_current] == ',':
            # ポインタの指し示す値に標準入力
            stack[stack_current] = ord(msvcrt.getch())
        elif cmd[cmd_current] == '[':
            # ポインタの指し示す値が0であれば、`]`にジャンプ
            if stack[stack_current] == 0:
                if (jump := cmd[cmd_current:].find(']')) != -1:
                    cmd_current += jump
                else:
                    cmd_current = jump
        elif cmd[cmd_current] == ']':
            # ポインタの指し示す値が0でなければ、`[`にジャンプ
            if stack[stack_current] != 0:
                cmd_current = cmd[:cmd_current].rfind('[')

        if cmd_current in {-1, CMD_END}:
            break
        else:
            cmd_current += 1

if __name__ == '__main__':
    while True:
        try:
            cmd = input('Brainf*ck> ')
            brainf_ck(cmd)
        except KeyboardInterrupt:
            print('End Brainf*ck...')
            break
        except:
            pass

動作は以下のようになる。
f:id:opaupafz2:20210812121757g:plain

終わりに

今回、「チューリング完全性が高い」という点に着目すれば、少なくともC、Excel VBA、Pythonはチューリング完全性が高い＝プログラミング言語であることを示すことができた。

しかし、「チューリング完全性が高い＝プログラミング言語ではない」という人も中にはいる。それには注意する必要がある。

とは言え、近年、個人的に「どれがプログラミング言語であるか？」という判定基準が曖昧になりすぎている、と感じている。であれば、「チューリング完全性が高い言語」を「プログラミング言語」だと定義してしまえば、単純明快になるのではないか？という思いがあったので、今回記事にした。

ちなみに今回、極力わかりやすい記事にするため、かなり省いたところがある。チューリング完全やチューリングマシンについてなど、気になったことがあれば調べてみると良いだろう。

*1:「チューリング完全である」とも言う

*2:自分があえて「チューリング完全である」と言わないのは、こういったところに起因している

*3:左右に折り返さない仕様のRule110もあるため。折り返す仕様のほうが実装が楽