ラングトンのアリ

講義外の自主的な学習内容を投稿する記事#1

今回はラングトンのアリです。

概要

ラングトンのアリは、単純な規則で記述される2次元チューリングマシンです。

・白いマス：アリは90°右に方向転換し、そのマスの色を黒に変更。
・黒いマス：アリは90°左に方向転換し、そのマスの色を白に変更。

これを繰り返して進みます。

実行環境

・Python
・Google Colab

以下のライブラリを使用しました

・matplotlib（可視化）
・numpy（配列操作）
・IPython.display（可視化更新）

シミュレーション

実行すると、アリが移動しながらマスの色を変化させていく様子をリアルタイムで観察できます。

・グリッドサイズ: 101×101
・ステップ数: 11,000
・可視化更新間隔: 500ステップごと

可視化結果

アリの軌跡は単調に見えますが、ある程度進むと特異な模様が現れることが特徴です。最終的には「ハイウェイ」と呼ばれる直線的なパターンが形成されます。

まずは色々準備

import matplotlib.pyplot as plt
import numpy as np
from IPython.display import clear_output
import time

そしてコード

# グリッドのサイズを設定
grid_size = 101
grid = np.zeros((grid_size, grid_size), dtype=int)
x, y = grid_size // 2, grid_size // 2
direction = 0  # 0: 上, 1: 右, 2: 下, 3: 左

# 移動ルール
dx = [0, 1, 0, -1]  # x方向の移動
dy = [-1, 0, 1, 0]  # y方向の移動

# シミュレーションのステップ数
steps = 11000

# 可視化を更新する間隔
update_interval = 500

# シミュレーションの実行
for step in range(steps):
    # 現在のセルの状態に応じて回転と色の変更
    if grid[y, x] == 0:  # 白
        direction = (direction - 1) % 4
        grid[y, x] = 1
    else:  # 黒
        direction = (direction + 1) % 4
        grid[y, x] = 0

    # アリを次のセルに移動
    x += dx[direction]
    y += dy[direction]

    # グリッドの範囲を超えないように調整
    x %= grid_size
    y %= grid_size

    # 可視化の更新
    if step % update_interval == 0 or step == steps - 1:
        clear_output(wait=True)
        plt.figure(figsize=(6, 6))
        plt.imshow(grid, cmap='binary', interpolation='nearest')
        plt.title(f"Step: {step}")
        plt.axis('off')
        plt.show()
        time.sleep(0.1)

結果