turing-complete

13熱度

3回答

圖靈語言完全無法解決暫停問題，對於一些非TC語言（例如正則表達式），可以輕鬆解決，因爲它總是停止。我想知道是否有任何語言既具有暫停而又不停止的能力，但承認可以確定是否停止的算法。

1熱度

2回答

我不太明白圖靈機的東西的整個想法。我目前的任務是製作一臺忙碌的海狸圖靈機。但我真的不明白的是它模擬輸入。那麼我會模擬什麼樣的輸入？例如，它問我3個繁忙的海狸機在磁帶上寫了多少個1？我確信我需要寫一個圖靈機，但是一旦我有了它，我該怎麼處理它？我應該用什麼字符串來模擬它？

1熱度

2回答

你知道什麼樣的優雅和圖靈整機？這本書有沒有一本書？

Lambda演算當然是非常優雅的，但是它不會打擾你在函數的輸入和輸出之間存在這種不對稱嗎？即你可以讓函數帶兩個參數（通過返回一個函數），但是你不能讓它返回兩個值。我不認爲我們可以在The Book中找到它。

45熱度

5回答

康威的生命遊戲爲什麼被列爲通用機器？

我最近在閱讀有關人造生命的文章，並且遇到了這樣的聲明，"Conway’s Game of Life demonstrates enough complexity to be classified as a universal machine."我只是粗略瞭解了universal machine是什麼，而維基百科只給了我和維基百科一樣接近理解。我想知道是否有人能夠對這個非常性感的陳述提出一些看法？