Skip to content

Posts MU-system #
Find similar titles

Gödel, Escher, Bach/Chapter I: The MU-puzzle에 나오는 production system인 MU-system을 Python으로 간단히 구현해봤다. (단, Rule 3과 4가 완전하지 않음)

#!python
import re

def main():
    axioms = ['MI']
    target = 'MU'
    rules = [rule1, rule2, rule3, rule4]

    theorems = axioms
    for _ in range(5):
        print theorems
        theorems = reduce(lambda x, y: x + y, [r(t) for t in theorems for r in rules], [])
        if target in theorems:
            print 'Found it!'
            break

def rule1(theorem):
    derivations = []
    if theorem[-1] == 'I':
        derivations.append(theorem + 'U')
    return derivations

def rule2(theorem):
    derivations = []
    m = re.match(r'^M(.+)$', theorem)
    if m:
        derivations.append('M' + m.group(1) * 2)
    return derivations

def rule3(theorem):
    derivations = []
    m = re.match(r'.*III.*', theorem)
    if m:
        derivations.append(theorem.replace('III', 'U'))
    return derivations

def rule4(theorem):
    derivations = []
    m = re.match(r'.*UU.*', theorem)
    if m:
        derivations.append(theorem.replace('UU', 'U'))
    return derivations

if __name__ == "__main__":
    main()

다음은 출력:

['MI']
['MIU', 'MII']
['MIUIU', 'MIIU', 'MIIII']
['MIUIUIUIU', 'MIIUIIU', 'MIIIIU', 'MIIIIIIII', 'MUI']

끝.

Incoming Links #

Related Articles #

Suggested Pages #

Other Posts #

0.0.1_20140628_0