Kalkulačka

Naprogramovat kalkulačku, která by uměla sčítat a násobit, je v jakémkoli obvyklém jazyce natolik jednoduché, že téměř není co programovat. Takováto kalkulačka však nevnikla tak, že by programátor „řekl“ počítači, co čísla a operace sčítání a násobení jsou. Pokus vytvořit kalkulačku právě tímto způsobem zde nabízím. Kalkulačka je tvořena jednak pravidly, jak upravovat formule na ekvivalentní tvar, a jednak mechanismem, který se snaží upravit formuli pomocí pravidel do nejjednoduššího tvaru, což provádí prohledáváním stavového prostoru funkcí. Pravidla, která definují, co jsou to čísla, jsou následující:

0 + 1 ↔ 1
1 + 1 ↔ 2
2 + 1 ↔ 3
3 + 1 ↔ 4
4 + 1 ↔ 5
5 + 1 ↔ 6
6 + 1 ↔ 7
7 + 1 ↔ 8
8 + 1 ↔ 9
9 + 1 ↔ 10
...

Pravidla, která definují, co jsou to operace sčítání a násobení, jsou tyto:

a + b → b + a
a * b → b * a
a + 0 ↔ a
0 → 0 * 0
a * 0 → 0
a * 1 ↔ a
a * (b * c) ↔ (a * b) * c
a + (b + c) ↔ (a + b) + c
a * (b + c) ↔ a * b + a * c

Např. úlohu vypočítat 2 * 2 řeší kalkulačka takto:

2 * 2 → 2 * (1 + 1) → 2 * 1 + 2 * 1 → 2 * 1 + 2 → 2 + 2 → 2 + 1 + 1 → 3 + 1 → 4.

Kalkulačka neprování žádné „skutečné“ výpočty, ale provádí pouze operace se symboly. K stávajícím pravidlům lze přidat další, např. pravidlo pro výpočet druhé odmocniny:

sqrt(a * a) → a.

Úlohu výpočtu sqrt(4) řeší kalkulačka takto:

sqrt(4) → sqrt(3 + 1) → sqrt(2 + 1 + 1) → sqrt(2 + 2) → sqrt(2 * 1 + 2) → sqrt(2 * 1 + 2 * 1) → sqrt(2 * (1 + 1)) → sqrt(2 * 2) → 2.

Při pokusu vypočítat sqrt(2) se algoritmus nikdy nezastaví.

Tato kalkulačka není nic, co by se dalo prakticky použít. ale ukazuje spoustu zajímavých problémů: Zastaví se kalkulačka pro každou vstupní formuli? Lze vždy určit, zda se kalkulačka zastaví, či ne? Lze dokázat, že nyní nebo po přidání nějakého nového pravidla nevznikne sporný systém? Atd.

Program je v pythonu a ke stažení je zde.