尋找非圖靈完成的語言

我對turing-machine和turing-complete語言有一點了解，但爲了更好地理解，有人可以給出非圖靈完整語言的示例嗎？（也許甚至不是圖靈的機器呢？）尋找非圖靈完成的語言

來源

2010-08-30 Tom Brito

正則表達式，在正式的定義，只包括：

級聯（AB）
無限重複（A *）
交替（A | B）
分組（（ ab）|（cd））

只能識別常規語言。圖靈完備的編程語言可以識別遞歸可枚舉的語言。

一個例子是，正則表達式不能告訴你，如果一個字符串由匹配的括號對組成：例如()(())被接受，而()((())()被拒絕，而圖靈完全編程語言可以。

（請注意，在現代編程語言的正則表達式比正則表達式的正式的學術定義，功能更強大。有些甚至會圖靈完整。）

來源

2010-08-30 12:42:04

例如，Perl regexp可以遞歸：http://www.catonmat.net/blog/recursive-regular-expressions PHP regexp具有/ e標誌來評估替換中的PHP表達式。 – 2010-08-31 17:13:16

@SHi：謝謝你，非常有趣！ – 2010-08-31 17:47:55

在Perl中看到一個正則表達式，它匹配的長度僅爲質數的字符串。使用回溯並花了相當長一段時間... – 2010-09-27 15:57:41

Regular languages - 那些可以被描述爲正則表達式的 - 是not Turing complete。

像XML和JSON這樣的標記語言（用於描述數據而不是計算）不是圖靈完整的。

來源

2010-08-30 12:37:58

數據和計算之間的差別是非常棘手。 [LaTeX]（http://stackoverflow.com/questions/2968411/ive-heard-that-latex-is-turing-complete-are-there-any-programs-written-in-latex）是圖靈完整的，儘管是一種文本處理語言。 – 2010-08-30 12:43:09

@Phillip：不完全公平，因爲LaTeX可以訪問所有TeX（至少部分）是通用語言。見Knuth的頁面，他在那裏回答「你最喜歡的語言是什麼？」的問題。 – Charles 2010-09-01 02:56:59

尋找非圖靈完成的語言

回答

相關問題