圖靈的完備性

所以如果語言符合某些標準，可以說語言是Turing complete，並且它可以完成另一種圖靈語言所能做的任何事情。圖靈的完備性

這是否意味着我可以在理論上使用JavaScript或Brainf_ck執行Google？

2010-09-11 maniac

我猜這即將被關閉（這是：http://stackoverflow.com/questions/3689311/stackoverflow-help-needed-closed）與此有關 – 2010-09-11 01:16:44

您只能實施Google搜索引擎通過爲Google工作並編寫他們實際使用的代碼。其他任何東西都不是Google搜索引擎。因此，一個更好的問題是，您是否可以在理論上實現這些語言中的搜索引擎*（類似於Google的搜索引擎）。 – jalf 2010-09-11 02:09:22

是的，任何他們可以計算，你可以用這些語言。但是這並不說明所需的內存或其他存儲空間的大小，運行速度或寫入或調試的便捷性。

來源

2010-09-11 01:12:52 poolie

我們將得到Chuck Norris編寫的代碼，然後我們可以跳過調試器... – 2010-09-27 15:56:09

您可以使用火柴盒和岩石製成的堆棧機器來執行Google。 YABBA-Dabba鬥？

來源

2010-09-11 01:15:12

當然，只要你有無限的磁帶和耐心。 – 2010-09-27 15:55:22

不，對於給定的例子，這是不可能的。圖靈完備性就是實現algorightms等等，它不會告訴你，如果你不能在其中實現任何軟件。谷歌主要依賴於他們的數據庫，你不能直接通過JavaScript進行操作，因爲沒有數據庫==沒有谷歌。

來源

2010-09-11 01:15:17

很好的答案。關鍵是圖靈完整性是計算問題的答案。它沒有提到I/O，存儲，與其他軟件的接口等。 – 2010-09-11 01:20:46

我不能只將數據庫放在內存中，假設我有無限的內存？ – maniac 2010-09-11 01:30:24

@maniac：是的。當然，如果你的軟件是不同的（例如，不使用數據庫），那麼你可能會問你是否「實施了Google」 – jalf 2010-09-11 02:08:21

除了I/O性能的問題之外，還有執行時間的問題。一臺圖靈機完成某項任務所需的步驟數可能比另一臺圖靈機完成相同工作所需的步數要長數百個數量級。因此，一臺機器完全有可能在幾分之一秒內完成一項任務，這將使另一臺機器忙碌直到宇宙結束;如果後一種機器即使在宇宙結束後仍能繼續運行，它可能會產生一個答案，但從實際的角度來看，儘管圖靈完備，後一機器仍然無法有效地解決問題。

來源

2010-09-11 05:17:02 supercat

圖靈的完備性

回答

相關問題