最後我們介紹一下『何謂 Thue 之改寫系統』？結束這個《系列》的第一篇。阿克塞爾‧圖厄【挪威語 Axel Thue】一位數學家，以研究丟番圖用『有理數』逼近『實數』問題以及開拓『組合數學』之貢獻而聞名。他於一九一四發表了『詞之群論問題』Word problem for group 啟始了一個今天稱之為『字串改寫系統』SRS String Rewriting System 的先河，如從現今的研究和發現來看，它與圖靈機的『停機問題』密切相關。上個千禧年之時，John Colagioia 用『Semi-Thue System』寫了一個『奧秘的』 esoteric 程式語言 Thue ，作者宣稱︰

Thue represents one of the simplest possible ways to construe 『constraint-based』基於約束 programming. It is to the constraint-based 『paradigm』典範 what languages like『 OISC 』── 單指令集電腦 One instruction set computer ── are to the imperative paradigm; in other words, it’s a 『tar pit』焦油坑.

─── 《THUE 之改寫系統《一》》

 

如何思考用 racket 語言建置之 MarioLANG 是否『圖靈完備』呢？

Turing completeness

In computability theory, a system of data-manipulation rules (such as a computer’s instruction set, a programming language, or a cellular automaton) is said to be Turing complete or computationally universal if it can be used to simulate any Turing machine. This means that this system is able to recognize or decide other data-manipulation rule sets. Turing completeness is used as a way to express the power of such data-manipulation rule set. The expression power of these grammars is captured in the Chomsky hierarchy. Virtually all programming languages today are Turing Complete. The concept is named after English mathematician and computer scientist Alan Turing.

A closely related concept is that of Turing equivalence – two computers P and Q are called equivalent if P can simulate Q and Q can simulate P. The Church–Turing thesis conjectures that any function whose values can be computed by an algorithm can be computed by a Turing machine, and therefore that if any real-world computer can simulate a Turing machine, it is Turing equivalent to a Turing machine. A universal Turing machine can be used to simulate any Turing machine and by extension the computational aspects of any possible real-world computer.^{[NB 1]}

To show that something is Turing complete, it is enough to show that it can be used to simulate some Turing complete system. For example, an imperative language is Turing complete if it has conditional branching (e.g., “if” and “goto” statements, or a “branch if zero” instruction; see one instruction set computer) and the ability to change an arbitrary amount of memory (e.g., the ability to maintain an arbitrary number of data items). Of course, no physical system can have infinite memory; but if the limitation of finite memory is ignored, most programming languages are otherwise Turing complete.

 

面對『 esoteric 』焦油坑，最好留之於『奧秘』乎？？

Thue (/ˈtuːeɪ/ TOO-ay) is an esoteric programming language invented by John Colagioia in early 2000. It is a meta-language that can be used to define or recognize Type-0 languages from the Chomsky hierarchy. Because it is able to define languages of such complexity, it is also Turing-complete itself. Thue is based on a nondeterministic string rewriting system called semi-Thue grammar, which itself is named after the Norwegian mathematician Axel Thue.

※ 註︰

catseye/Thue

Cat’s Eye Technologies’ distribution of John Colagioia’s Thue programming language http://catseye.tc/node/Thue

The Thue Programming Language

This is Cat’s Eye Technologies’ distribution of Thue, an esoteric programming language designed by John Colagioia. Thue is a non-deterministic string-rewriting language, based on a formalism called a semi-Thue system, but also including some programming-oriented features, like input and output.

The specification can be found in the file thue.txt in the doc directory.

John’s implementation of the language, in C, is in the file thue.c in the src directory, and can, for all intents and purposes, be considered the reference implementation. There is no Makefile but an executable can be built by running the included build.sh script, which is trivial.

In the src directory, there are also two other implementation of Thue:

• thue.py, in Python, written by Frédéric van der Plancke
• thue.rb, in Ruby, written by Chris Pressey

There is an assortment of example Thue programs in the eg directory. The credits for these are as follows:

• add_bin.t: Frédéric van der Plancke
• edgcase?.t: Chris Pressey
• truth-machine.t: Keymaker
• quine.t: TSUYUSATO Kitsune
• all others: John Colagioia

More information on Thue can be found on the esolangs.org wiki entry for Thue.

Contents in this distribution are “essentially in the public domain” (scare quotes intentional.) See the file LICENSE for more information.

 

那邊『同一性』identity 問題，嘎天震響已久！

這個『同一性』identity 問題，在邏輯學上叫做『同一律』，與真假不相容的『矛盾律』齊名︰

。

這裡『邱奇－圖靈論題』尚未證明！！

同樣的問題也發生在計算機科學中的『同等』之『可計算性』問題之上，如果有甲和乙兩台計算機，或者說假使有  A 與 B 兩個程式語言，你將如何區分它們彼此的『計算的功能』或者『表達之能力』的呢？有一個尚未被證明的著名『猜測』，一個由『 λ 運算』之創始人 Church 和『圖靈機』的發明者 Turing 共通設想的『論題』 thesis ︰

 In computability theory,  the Church–Turing thesis ( also known as the Turing–Church thesis,  the Church–Turing conjecture,  Church’s thesis,  Church’s conjecture,  and Turing’s thesis) is a combined hypothesis ( “thesis” ) about the nature of functions whose values are effectively calculable;  or,  in more modern terms,  functions whose values are algorithmically computable.  In simple terms,  the Church–Turing thesis states that a function is algorithmically computable if and only if it is computable by a Turing machine.

因此任何計算機或程式語言只要能夠『模擬』simulate 『圖靈機』，按造上述猜測，它們都具有一樣的『計算能力』，所以 Thue 之改寫系統也具有同等的計算能力。如果你試著去讀 John Colagioia 所寫的 Thue 語言的  python  原始碼，不知會不會驚訝於包含著註解，程式全長只有二百九十二行，但它和 python 語言的計算能力竟是一樣的。但是不要『誤解』這個計算能力的『相當性』，並不代表著『程式寫作』的『方便性』或『清晰性』，就像 Log 『計算尺』的發明，是因為在用紙筆計算的時代，大數的乘除有時甚至是不可能的。舉個例說計算 ，假使真的一個一個的乘，然後再加不知要不要花上『千萬年』，但是如果使用 Log ，可能是『幾分鐘』的事。也許有人反對說，兩個結果不一樣，一個是『正確的』數，另一個只是『近似的』值，這也難怪有人不得不用 『奧秘的』語法寫一個『神奇的』程式︰『我愛你一世，唉！我氣你愛』，看看會不會發生不可判定之『當機』問題。

一九七二年布萊恩‧柯林漢 Brian Wilson Kernighan  於貝爾實驗室撰寫《Introduction to the Language B》的內部技術文件時，寫了一個『hello, world』的範例程式。其後他與 丹尼斯‧里奇 Dennis M. Ritchie 合著的《The C Programming Language》也保留了這個範例程式。不知怎的這成了一個『傳統』，成了初學者所編寫的第一個程式。現今流行的寫法是『Hello, World!』，不知柯林漢會不會抱怨這是是那個嗎？它的原典是︰

hello, world

，裡頭所有字母全是小寫，『 , 』之後有一『空白』。

Colagioia 的 Thue 語言是 semi-Thue 的字串改寫系統 ── 包含子字串擴充之 系統 ──，它的程式架構只有兩個部份 ── 字串改寫規則定義和初始字串構成 ──；其中『  字串改寫規則』的定義寫作︰

u ::= v

它提供了輸出入功能的『預設』符號 ，用『 ~ 』表示輸出和『 ::: 』表輸入，它們的規定是︰

標籤字串 ::= ~取代標籤之字串

， 意義是將『標籤字串』改寫成『空字串』，把接在『 ~ 』之後的『取代標籤之字串』輸出到『標準輸出』── 一般是顯示器 ──。

標籤字串 ::=:::

，意義是將『標籤字串』由『標準輸入』── 一般是鍵盤 ── 之輸入取代。

改寫規則定義的『結束列』是一條『空白的規則』定義列︰

::=

，它結束了改寫規則之定義，開啟了『初始字串』的構成。Thue  語言方便讓你可以寫多列的字串，它的語言解譯器會自動將它們序連串成一整個『初始字串』。

一個程式語言的寫作規則只有『四條』，它真的『能寫程式』嗎？當然能，而且可以用『中文化』的『符號』或者說『概念』來寫程式，舉個例子『將一個使用者輸入的二進制之數加一』可以寫成︰

1後繼者::=1加一
0後繼者::=1
01加一::=10
11加一::=1加一0
後繼者0::=後繼者
後繼者1加一::=10
□::=:::
::=
後繼者□後繼者

，這裡的『後繼者』第一個意思是一種自然數的概念，是義大利數學家 Giuseppe Peano 提出的概念︰

自然數 n 的後繼者是 n + 1

，假使它用在『0』與『1』的符號之後，表示將『之前』的數『加一』；如果它用在『0』與『1』的符號之前，是對『之後』之數作最後的『進位』處理。假使你試著用 Step 按鍵，一步一步的觀察，你將能發現這個 Thue 程式的『奧秘』。事實上有許多的『概念』可以用『各種』之『表述』形式，只看用這個概念的人到底是如何設想的呢？更不要說『人類的語言』之本身當然是能『寫作程式』的啊！！

有許多的人以為『確定性』要比『隨機性』要困難的多，其實是『隨機性』真實要困難的多。試想你要怎麽『產生』它的呢？再想一想所謂的『亂數產生器』Random number generation 的方法，它的背後有個『公式』，『隨機』真是能有公式的嗎？所以通常會將之冠以『 pseudo 』一詞，表達著不是像《易經》說的那樣『陰陽不測謂之神』。Thue 之改寫系統的『不確定性』是否就能『心誠則靈』的呢？不如就『擲個筊』吧！

擲筊::=~聖杯
擲筊::=~無杯
誠心祈求::=誠心擲筊祈求
::=
誠心擲筊祈求

── 原來『道可道，非常道』一樣是『程式之道』的啊！！ ──

─── 摘自《THUE 之改寫系統《三》》

 

或該擲筊耶◎