class TuringMachine:
    """チューリングマシンのシミュレータ"""
 
    def __init__(self, states, input_alphabet, tape_alphabet,
                 transition_function, start_state,
                 accept_state, reject_state):
        self.states = states
        self.input_alphabet = input_alphabet
        self.tape_alphabet = tape_alphabet
        self.transition = transition_function
        self.start_state = start_state
        self.accept_state = accept_state
        self.reject_state = reject_state
 
    def run(self, input_string, max_steps=10000):
        """入力文字列に対してTMを実行する"""
        # テープの初期化
        tape = list(input_string) + ['B']
        head = 0
        state = self.start_state
        steps = 0
 
        history = []
 
        while steps < max_steps:
            # 現在の設定を記録
            history.append({
                'step': steps,
                'state': state,
                'head': head,
                'tape': ''.join(tape)
            })
 
            # 受理・拒否の判定
            if state == self.accept_state:
                return 'accept', history
            if state == self.reject_state:
                return 'reject', history
 
            # テープの拡張（必要に応じて）
            if head < 0:
                tape.insert(0, 'B')
                head = 0
            if head >= len(tape):
                tape.append('B')
 
            # 遷移の実行
            current_symbol = tape[head]
            key = (state, current_symbol)
 
            if key not in self.transition:
                return 'reject', history
 
            new_state, write_symbol, direction = self.transition[key]
            tape[head] = write_symbol
            state = new_state
            head += 1 if direction == 'R' else -1
            steps += 1
 
        return 'loop', history  # max_steps超過
 
 
# 具体例: 2進数を1増やすチューリングマシン
def create_binary_increment_tm():
    """2進数のインクリメントを行うTM"""
    states = {'q0', 'q1', 'q2', 'q_accept'}
    input_alphabet = {'0', '1'}
    tape_alphabet = {'0', '1', 'B'}
 
    # q0: 右端に移動
    # q1: 右端から左へ、繰り上がり処理
    # q2: 繰り上がり完了、左端に戻る
    transition = {
        # 右端まで移動
        ('q0', '0'): ('q0', '0', 'R'),
        ('q0', '1'): ('q0', '1', 'R'),
        ('q0', 'B'): ('q1', 'B', 'L'),
 
        # インクリメント処理（右から左へ）
        ('q1', '1'): ('q1', '0', 'L'),  # 繰り上がり
        ('q1', '0'): ('q2', '1', 'L'),  # 繰り上がり停止
        ('q1', 'B'): ('q_accept', '1', 'R'),  # 先頭に繰り上がり
 
        # 完了、左端に戻る
        ('q2', '0'): ('q2', '0', 'L'),
        ('q2', '1'): ('q2', '1', 'L'),
        ('q2', 'B'): ('q_accept', 'B', 'R'),
    }
 
    return TuringMachine(
        states, input_alphabet, tape_alphabet,
        transition, 'q0', 'q_accept', 'q_reject'
    )
 
 
# 実行例
tm = create_binary_increment_tm()
 
test_cases = ['0', '1', '10', '11', '101', '111', '1111']
for tc in test_cases:
    result, history = tm.run(tc)
    final_tape = history[-1]['tape'].rstrip('B')
    print(f"  {tc} → {final_tape} ({result})")
 
# 出力:
#   0 → 1 (accept)
#   1 → 10 (accept)
#   10 → 11 (accept)
#   11 → 100 (accept)
#   101 → 110 (accept)
#   111 → 1000 (accept)
#   1111 → 10000 (accept)

class UniversalTuringMachine:
    """万能チューリングマシンの概念的実装"""
 
    def __init__(self):
        pass
 
    def encode_tm(self, tm):
        """チューリングマシンをエンコードする（ゲーデル数化）"""
        # 状態、アルファベット、遷移関数をシリアライズ
        encoding = {
            'states': list(tm.states),
            'input_alphabet': list(tm.input_alphabet),
            'tape_alphabet': list(tm.tape_alphabet),
            'transitions': {},
            'start_state': tm.start_state,
            'accept_state': tm.accept_state,
            'reject_state': tm.reject_state
        }
 
        for (state, symbol), (new_state, write, direction) in tm.transition.items():
            key = f"{state},{symbol}"
            encoding['transitions'][key] = {
                'new_state': new_state,
                'write': write,
                'direction': direction
            }
 
        return encoding
 
    def simulate(self, encoded_tm, input_string, max_steps=10000):
        """エンコードされたTMを入力文字列上でシミュレートする"""
        # デコード
        transitions = {}
        for key, value in encoded_tm['transitions'].items():
            state, symbol = key.split(',')
            transitions[(state, symbol)] = (
                value['new_state'],
                value['write'],
                value['direction']
            )
 
        # シミュレーション
        tape = list(input_string) + ['B']
        head = 0
        state = encoded_tm['start_state']
 
        for step in range(max_steps):
            if state == encoded_tm['accept_state']:
                return 'accept'
            if state == encoded_tm['reject_state']:
                return 'reject'
 
            if head < 0:
                tape.insert(0, 'B')
                head = 0
            if head >= len(tape):
                tape.append('B')
 
            key = (state, tape[head])
            if key not in transitions:
                return 'reject'
 
            new_state, write, direction = transitions[key]
            tape[head] = write
            state = new_state
            head += 1 if direction == 'R' else -1
 
        return 'timeout'  # ステップ数超過（停止しない可能性）
 
 
# 万能TMの意義:
# 1. 一つのマシンで全てのプログラムを実行できる
# 2. 現代のコンピュータ（ノイマン型）の理論的基礎
# 3. 「プログラムもデータとして扱える」という概念の原型
# 4. コンパイラ、インタプリタの理論的正当化

# チューリング完全性の最小例: BFインタプリタ
# BFは8命令のみでチューリング完全
 
def bf_interpreter(code, input_data=""):
    """Brainf*ckインタプリタ — チューリング完全な最小言語"""
    tape = [0] * 30000
    ptr = 0
    pc = 0
    input_pos = 0
    output = []
 
    # ブラケットの対応表を構築
    brackets = {}
    stack = []
    for i, c in enumerate(code):
        if c == '[':
            stack.append(i)
        elif c == ']':
            if stack:
                j = stack.pop()
                brackets[j] = i
                brackets[i] = j
 
    max_steps = 1000000
    steps = 0
 
    while pc < len(code) and steps < max_steps:
        cmd = code[pc]
        if cmd == '>':
            ptr = (ptr + 1) % 30000
        elif cmd == '<':
            ptr = (ptr - 1) % 30000
        elif cmd == '+':
            tape[ptr] = (tape[ptr] + 1) % 256
        elif cmd == '-':
            tape[ptr] = (tape[ptr] - 1) % 256
        elif cmd == '.':
            output.append(chr(tape[ptr]))
        elif cmd == ',':
            if input_pos < len(input_data):
                tape[ptr] = ord(input_data[input_pos])
                input_pos += 1
            else:
                tape[ptr] = 0
        elif cmd == '[':
            if tape[ptr] == 0:
                pc = brackets[pc]
        elif cmd == ']':
            if tape[ptr] != 0:
                pc = brackets[pc]
 
        pc += 1
        steps += 1
 
    return ''.join(output)
 
 
# Hello World in BF
hello_bf = (
    "++++++++[>++++[>++>+++>+++>+<<<<-]"
    ">+>+>->>+[<]<-]>>.>---.+++++++..+++."
    ">>.------------.<<+++++++++++++++.>."
    "+++.------.--------.>>+.>++."
)
print(bf_interpreter(hello_bf))  # "Hello World!\n"
 
# BFがチューリング完全である理由:
# - 無限（十分に大きい）テープ → 任意の記憶
# - ループ構造 ([...]) → 繰り返し
# - 条件分岐 ([]でゼロチェック) → 条件
# - データの読み書き (+, -, >, <) → 状態操作

# 停止問題の不可能性を示すPython風の疑似コード
 
def hypothetical_halts(program_source, input_data):
    """仮に存在するとする停止判定関数（実際には存在しない）"""
    # program_source をinput_data で実行した場合に
    # 停止するかどうかを判定する
    # ... 魔法の実装 ...
    pass
 
def diagonal(program_source):
    """矛盾を引き起こすプログラム"""
    if hypothetical_halts(program_source, program_source):
        # 停止すると判定されたら、無限ループ
        while True:
            pass
    else:
        # 停止しないと判定されたら、停止
        return
 
# diagonal のソースコードを取得
diagonal_source = inspect.getsource(diagonal)
 
# diagonal(diagonal_source) を実行するとどうなるか？
#
# 場合1: hypothetical_halts(diagonal_source, diagonal_source) == True
#   → diagonal は停止すると判定された
#   → しかしdiagonalは無限ループに入る
#   → 停止しない → 矛盾
#
# 場合2: hypothetical_halts(diagonal_source, diagonal_source) == False
#   → diagonal は停止しないと判定された
#   → しかしdiagonalはreturnで停止する
#   → 停止する → 矛盾
#
# どちらの場合も矛盾 → hypothetical_halts は存在し得ない

# 停止問題の帰結を示す具体例
 
# 例1: デッドコード検出の限界
def is_dead_code(function_body, line_number):
    """
    指定行が到達不能かを完全に判定することは不可能
 
    理由: 以下のようなコードを考える
    """
    pass
 
def example_with_undecidable_reachability():
    """到達可能性が決定不能な例"""
    x = compute_goldbach()  # ゴールドバッハ予想が真なら停止
    if x:
        print("この行は到達可能か？")  # 未解決の数学的問題に依存
        # → デッドコードかどうかを判定することは
        #   ゴールドバッハ予想を証明/反証することに等しい
 
def compute_goldbach():
    """ゴールドバッハ予想の反例を探す"""
    n = 4
    while True:
        if n % 2 == 0 and not is_sum_of_two_primes(n):
            return n  # 反例が見つかれば停止
        n += 2
    # 反例がなければ永遠に停止しない
 
def is_sum_of_two_primes(n):
    """nが2つの素数の和で表せるかチェック"""
    for i in range(2, n):
        if is_prime(i) and is_prime(n - i):
            return True
    return False
 
def is_prime(n):
    """素数判定"""
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True
 
 
# 例2: 静的解析の保守的近似
class ConservativeAnalyzer:
    """保守的な静的解析器の例"""
 
    def check_division_by_zero(self, code_ast):
        """
        ゼロ除算の可能性を保守的にチェック
 
        完璧な検出は不可能なので:
        - 偽陽性（false positive）は許容する
        - 偽陰性（false negative）は許容しない
        """
        warnings = []
 
        for node in self.walk(code_ast):
            if self.is_division(node):
                divisor = self.get_divisor(node)
                if not self.can_prove_nonzero(divisor):
                    # ゼロでないことを証明できない → 警告
                    # （実際にはゼロにならないかもしれないが）
                    warnings.append(f"Line {node.line}: 潜在的なゼロ除算")
 
        return warnings
 
    def can_prove_nonzero(self, expr):
        """式がゼロでないことを証明できるか（保守的）"""
        # 定数の場合
        if self.is_constant(expr) and self.eval_constant(expr) != 0:
            return True
        # abs(x) > 0 のようなパターン
        if self.matches_positive_pattern(expr):
            return True
        # それ以外は証明できない（保守的にFalse）
        return False

# 決定可能な問題の例
 
# 1. 有限オートマトンの受理問題
# A_DFA = { ⟨B, w⟩ | DFA Bが文字列wを受理する }
class DFA:
    """決定性有限オートマトン"""
    def __init__(self, states, alphabet, transitions, start, accepts):
        self.states = states
        self.alphabet = alphabet
        self.transitions = transitions  # (state, symbol) -> state
        self.start = start
        self.accepts = accepts
 
    def accepts_string(self, w):
        """O(|w|) で判定可能 — 常に停止する"""
        state = self.start
        for symbol in w:
            state = self.transitions.get((state, symbol))
            if state is None:
                return False
        return state in self.accepts
 
 
# 2. 文脈自由文法の所属判定
# A_CFG = { ⟨G, w⟩ | CFG Gが文字列wを生成する }
def cyk_algorithm(grammar, string):
    """CYKアルゴリズム — O(n³|G|) で判定可能"""
    n = len(string)
    if n == 0:
        return grammar.start in grammar.nullable
 
    # 初期化
    table = [[set() for _ in range(n)] for _ in range(n)]
 
    # 長さ1の部分文字列
    for i in range(n):
        for lhs, rhs_list in grammar.rules.items():
            for rhs in rhs_list:
                if len(rhs) == 1 and rhs[0] == string[i]:
                    table[i][i].add(lhs)
 
    # 長さ2以上の部分文字列
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):
                for lhs, rhs_list in grammar.rules.items():
                    for rhs in rhs_list:
                        if len(rhs) == 2:
                            B, C = rhs
                            if B in table[i][k] and C in table[k+1][j]:
                                table[i][j].add(lhs)
 
    return grammar.start in table[0][n-1]
 
 
# 3. 有限オートマトンの等価性判定
# EQ_DFA = { ⟨A, B⟩ | DFA AとBが同じ言語を認識する }
def dfa_equivalence(dfa_a, dfa_b):
    """
    2つのDFAが等価かどうかを判定
    積オートマトンを構成し、対称差が空かチェック
    常に停止する — 決定可能
    """
    # 対称差 = (L(A) - L(B)) ∪ (L(B) - L(A))
    # 対称差が空 ↔ L(A) = L(B)
    symmetric_diff = construct_symmetric_difference(dfa_a, dfa_b)
    return is_empty(symmetric_diff)
 
def is_empty(dfa):
    """DFAの言語が空かどうかをBFSで判定"""
    visited = set()
    queue = [dfa.start]
    visited.add(dfa.start)
 
    while queue:
        state = queue.pop(0)
        if state in dfa.accepts:
            return False  # 受理状態に到達可能 → 空でない
        for symbol in dfa.alphabet:
            next_state = dfa.transitions.get((state, symbol))
            if next_state and next_state not in visited:
                visited.add(next_state)
                queue.append(next_state)
 
    return True  # 受理状態に到達不能 → 空
 
 
# 4. グラフの連結性判定
def is_connected(graph):
    """グラフが連結かどうかを判定 — O(V + E)"""
    if not graph:
        return True
 
    visited = set()
    start = next(iter(graph))
 
    def dfs(node):
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs(neighbor)
 
    dfs(start)
    return len(visited) == len(graph)

# ポスト対応問題（PCP）の具体例
 
def pcp_brute_force(dominoes, max_length=10):
    """
    PCPを力任せに探索する（一般には停止しない可能性がある）
 
    ドミノの例:
    [(ab, b), (b, ab), (a, aa)]
 
    解: 1,2,1,3 → ababba = ababba ✓
    """
    from itertools import product
 
    for length in range(1, max_length + 1):
        for combo in product(range(len(dominoes)), repeat=length):
            top = ''.join(dominoes[i][0] for i in combo)
            bottom = ''.join(dominoes[i][1] for i in combo)
            if top == bottom:
                return list(combo), top
 
    return None  # max_length以内では解が見つからない
 
# 実行例
dominoes = [('ab', 'b'), ('b', 'ab'), ('a', 'aa')]
result = pcp_brute_force(dominoes, max_length=8)
if result:
    indices, matched = result
    print(f"解: {indices}")
    print(f"一致文字列: {matched}")
 
# PCPが決定不能である意味:
# - 解があるかどうかを判定するアルゴリズムは存在しない
# - 解がある場合は力任せ探索で見つかる（半決定可能）
# - 解がない場合は永遠に探索が終わらない

# 半決定可能性の実装例
 
import threading
import time
 
class SemiDecider:
    """半決定的判定器"""
 
    def check_halts(self, program, input_data, timeout=None):
        """
        プログラムが停止するかをチェック（半決定的）
 
        - 停止する場合: True を返す（有限時間で）
        - 停止しない場合: timeout まで待って None を返す
          （timeout なしなら永遠に待つ）
        """
        result = [None]
        error = [None]
 
        def run_program():
            try:
                exec(program, {'input': input_data})
                result[0] = True
            except Exception as e:
                error[0] = e
                result[0] = True  # 例外で終了 = 停止した
 
        thread = threading.Thread(target=run_program)
        thread.daemon = True
        thread.start()
        thread.join(timeout=timeout)
 
        if thread.is_alive():
            return None  # タイムアウト（停止するかどうか不明）
        return result[0]
 
 
# 並列実行による決定可能化の例
def parallel_decide(recognizer_l, recognizer_l_complement, input_data):
    """
    LとL̄の両方の認識器がある場合、決定器を構築できる
 
    前提: LとL̄がともに半決定可能
    結論: Lは決定可能
    """
    result = [None]
 
    def run_l():
        if recognizer_l(input_data):
            result[0] = True  # w ∈ L
 
    def run_l_complement():
        if recognizer_l_complement(input_data):
            result[0] = False  # w ∉ L
 
    t1 = threading.Thread(target=run_l)
    t2 = threading.Thread(target=run_l_complement)
    t1.daemon = True
    t2.daemon = True
    t1.start()
    t2.start()
 
    # どちらかが停止するまで待つ（必ずどちらかは停止する）
    while result[0] is None:
        time.sleep(0.001)
 
    return result[0]

# 帰着の具体例: 停止問題 → 全域性問題
 
# 全域性問題: プログラムPが全ての入力で停止するか？
# TOTAL = { ⟨P⟩ | Pは全ての入力で停止する }
 
# 定理: TOTAL は決定不能
 
# 証明: HALT ≤ₘ TOTAL̄ を示す（TOTALの補集合に帰着）
 
def reduce_halt_to_total(program_p, input_w):
    """
    停止問題のインスタンス (P, w) を
    全域性問題のインスタンス Q に変換する
    """
    # 新しいプログラムQを構築:
    # Q(x) = P(w) を実行して停止したら停止、
    #         xは無視する
 
    q_source = f"""
def Q(x):
    # xは無視して、P(w)を実行する
    {program_p}({input_w})
    return  # P(w)が停止すればQも停止
"""
 
    # P(w)が停止する → Q(x)は全ての入力xで停止 → Q ∈ TOTAL
    # P(w)が停止しない → Q(x)はどの入力でも停止しない → Q ∉ TOTAL
 
    # つまり: (P, w) ∈ HALT ⟺ Q ∈ TOTAL
 
    return q_source
 
 
# 帰着の例2: 停止問題 → 等価性問題
 
# 等価性問題: 2つのTMが同じ言語を認識するか？
# EQ_TM = { ⟨M₁, M₂⟩ | L(M₁) = L(M₂) }
 
def reduce_halt_to_eq(program_p, input_w):
    """
    停止問題のインスタンス (P, w) を
    等価性問題のインスタンス (M₁, M₂) に変換する
    """
    # M₁: 全ての入力を拒否する（空言語）
    m1 = lambda x: False
 
    # M₂: P(w)を実行し、停止したら全ての入力を拒否
    #      停止しなければループ
    def m2(x):
        # P(w) を実行
        exec(program_p, {'input': input_w})
        # P(w)が停止した場合のみここに到達
        return False  # 拒否
 
    # P(w)が停止する → L(M₂) = ∅ = L(M₁) → (M₁,M₂) ∈ EQ_TM
    # P(w)が停止しない → M₂は全入力でループ → L(M₂)は認識不能
    #                   → L(M₁) ≠ L(M₂) → (M₁,M₂) ∉ EQ_TM
 
    return m1, m2

# ライスの定理の実務的意味
 
class ProgramAnalyzer:
    """
    ライスの定理により、以下の分析は全て一般には不可能
    """
 
    def does_program_always_return_positive(self, program):
        """プログラムが常に正の値を返すか？ → 決定不能"""
        raise UndecidableError("ライスの定理により不可能")
 
    def does_program_use_network(self, program):
        """
        プログラムがネットワークにアクセスするか？
 
        注意: これは「構文的」にチェックすれば決定可能
        （importやsocket呼び出しの有無を確認）
 
        しかし「意味的」にチェックは決定不能
        （動的生成されたコードがネットワークアクセスする場合）
        """
        # 構文的チェック（保守的な近似）は可能
        return 'socket' in program or 'requests' in program
 
    def is_program_equivalent_to(self, program_a, program_b):
        """2つのプログラムが同じ関数を計算するか？ → 決定不能"""
        raise UndecidableError("ライスの定理により不可能")
 
    def does_program_terminate_for_all_inputs(self, program):
        """プログラムが全入力で停止するか？ → 決定不能"""
        raise UndecidableError("ライスの定理により不可能")
 
 
class UndecidableError(Exception):
    """決定不能な問題に対するエラー"""
    pass
 
 
# 実務での対処法:
#
# 1. 保守的近似（Sound but Incomplete）
#    - 「安全でない可能性がある」 → 警告を出す
#    - 偽陽性はあるが、見逃しはない
#    例: Rust の借用チェッカー
#
# 2. 楽観的近似（Complete but Unsound）
#    - 「おそらく安全」 → 通す
#    - 見逃しはあるが、偽陽性はない
#    例: 動的型付き言語の実行時チェック
#
# 3. 制限付き正確解
#    - 問題の範囲を制限して、その範囲では正確に判定
#    例: 有界モデル検査（bounded model checking）
#
# 4. 対話的検証
#    - ユーザーにヒントや証明を提供してもらう
#    例: 対話型定理証明器（Coq, Isabelle, Lean）

# クワイン: 自分自身のソースコードを出力するプログラム
# 再帰定理の構成的証明の具体例
 
# Python のクワイン（最小版）
s='s=%r;print(s%%s)';print(s%s)
 
# より読みやすい版
def quine():
    """
    再帰定理により、任意のプログラミング言語で
    クワインを構築できることが保証されている
    """
    # 2部構成: データ部（A）とコード部（B）
    # A = Bのテキスト表現
    # B = Aを使って全体を再構成するコード
 
    A = 'def quine():\n    A = %r\n    B = A %% A\n    print(B)\nquine()'
    B = A % A
    print(B)
 
# 各言語のクワインの例:
 
# JavaScript
js_quine = '(function q(){console.log("("+q+")()")})()'
 
# Ruby
ruby_quine = 's="s=%p;puts s%%s";puts s%s'
 
# C言語
c_quine = '''
#include <stdio.h>
int main(){char*s="#include <stdio.h>%cint main(){char*s=%c%s%c;printf(s,10,34,s,34);}";printf(s,10,34,s,34);}
'''
 
# クワインの構造:
# 1. データ部: プログラム全体のテンプレート（一部が空白）
# 2. コード部: 空白部分にデータ部自身を埋め込んで出力
#
# 再帰定理はこの構成が常に可能であることを保証する

# 計算可能性理論がプログラミング言語設計に与える影響
 
# 1. 全域性の保証 vs チューリング完全性
#    全ての入力で停止することを保証する言語は
#    チューリング完全ではない
 
# Agda（全域関数型言語）の例（概念的）:
# - 全ての関数は停止が保証される
# - 再帰は構造的に減少する引数が必要
# - チューリング完全ではないが、実用上は十分
 
# 概念的な全域再帰の例
def structural_recursion(n: int) -> int:
    """構造的再帰: 引数が必ず減少する → 停止が保証"""
    if n <= 0:
        return 0
    return 1 + structural_recursion(n - 1)  # n は必ず減少
 
def non_structural(n: int) -> int:
    """非構造的再帰: 停止が保証されない"""
    if n == 1:
        return 0
    if n % 2 == 0:
        return 1 + non_structural(n // 2)
    else:
        return 1 + non_structural(3 * n + 1)  # コラッツ予想
    # 全ての入力で停止するかは未解明！
 
 
# 2. 型推論の決定可能性
#
# Hindley-Milner型推論（ML, Haskell98）: 決定可能
# - 主要型（principal type）が存在
# - 完全な型推論が可能
#
# System F（多相λ計算）の型推論: 決定不能
# - 明示的な型注釈が必要
# - Haskell の一部の拡張機能で該当
#
# TypeScript の型推論: 意図的にチューリング完全
# - 条件型（Conditional Types）+ 再帰型 = チューリング完全
# - 型チェックが停止しない型定義が書ける
 
# TypeScript の型レベル計算の例（概念的）:
# type Fibonacci<N extends number> = ...
# → 型チェッカーが無限ループする可能性
 
 
# 3. マクロシステムと計算可能性
#
# C のプリプロセッサ: チューリング完全ではない
# → マクロ展開は必ず停止する
#
# Rust のマクロ: 制限的なチューリング完全性
# → 再帰深度の制限あり（#![recursion_limit = "..."]）
#
# Template Haskell: チューリング完全
# → コンパイル時に任意の計算が可能
#
# Lisp マクロ: チューリング完全
# → コンパイル時（マクロ展開時）にループ可能

# コンパイラ最適化と計算可能性の限界
 
class CompilerOptimizer:
    """コンパイラ最適化の限界を示す例"""
 
    def dead_code_elimination(self, code):
        """
        デッドコード除去
 
        完璧なデッドコード除去は決定不能（ライスの定理）
        実用的なコンパイラは保守的な近似を使用
        """
        # 到達不能なコード:
        # - 常にFalseの条件分岐 → 検出可能（定数畳み込み）
        # - 関数の戻り値に依存する条件 → 一般には検出不能
        pass
 
    def constant_propagation(self, code):
        """
        定数伝播
 
        「この変数は常に定数値か？」は一般に決定不能
        しかし、多くの実用的なケースでは判定可能
        """
        pass
 
    def loop_optimization(self, code):
        """
        ループ最適化
 
        「このループは有限回で終了するか？」は決定不能
        → ループ不変式の自動発見にも限界がある
 
        しかし:
        - for i in range(n): ... → 明らかに有限
        - while condition: ... → 一般には不明
        """
        pass
 
    def alias_analysis(self, code):
        """
        エイリアス解析
 
        「この2つのポインタは同じメモリを指すか？」
        → 完璧な解析は決定不能
        → 保守的な近似（Andersen, Steensgaard等）
 
        実務的影響:
        - Cの restrict キーワード: プログラマがヒントを提供
        - Rust の借用規則: コンパイラが安全に追跡可能
        """
        pass
 
 
# 最適化の実例: GCC vs 計算可能性の限界
 
# 以下のコードのデッドコード除去:
def optimization_example():
    x = complex_computation()  # 副作用があるか不明
    if x > 0:
        print("positive")
    else:
        print("non-positive")
 
    # コンパイラが知りたいこと:
    # 1. complex_computation() は常に正の値を返すか？ → 決定不能
    # 2. complex_computation() に副作用はあるか？ → 決定不能
    # 3. このif文はどちらの分岐が取られるか？ → 決定不能
 
    # 結果: コンパイラは両方の分岐を残す（保守的）

"""
演習: Pythonでクワインを構築せよ。
 
条件:
1. 外部ファイルを読まない
2. 空のプログラムではない
3. 自分自身のソースコードを正確に出力する
 
ヒント: 2部構成（データ部 + コード部）を使う
 
解答例:
"""
 
# 方法1: %r フォーマットを使用
s='s=%r;print(s%%s)';print(s%s)
 
# 方法2: f-stringを使用（Python 3.12+）
# exec(s:="print(f'exec(s:={chr(34)}{s}{chr(34)})')")
 
# 方法3: 理解しやすい版
def make_quine():
    """クワインの構造を理解するための段階的構築"""
 
    # ステップ1: テンプレート（自分自身の骨格）
    template = 'template = {!r}\nprint(template.format(template))'
 
    # ステップ2: テンプレートに自身を埋め込んで出力
    print(template.format(template))
 
# 出力結果が入力と同じであることを確認
make_quine()