vy32
2020-03-15 01:21:45 UTC
我正在尋找不確定性圖靈機的第一個參考。 1936年的論文“關於可計算數字”中沒有提及它們。
我正在尋找不確定性圖靈機的第一個參考。 1936年的論文“關於可計算數字”中沒有提及它們。
根據SEP， Rabin和Scott在有限自動機及其決策問題中引入了不確定性（IBM Journal of Research and Development，3（2）114–125，1959年） ）。他們的主要結果是，它不會導致更強的可計算性概念：
“ 在第一章中使用的自動機在其磁帶讀取操作中是嚴格確定的，這是唯一確定的根據移動表，由於在任何特定情況下機器都有一種唯一的方式來改變其狀態，鑑於需要大量的內部狀態，因此要求所有機器都採用這種形式可能會導致相當繁瑣的細節在本節中，我們介紹了不確定性自動機的概念，並顯示了由這種機器定義的任何一組磁帶也可以由普通自動機定義。這些機器的主要優點是數量很少在許多情況下它們需要內部狀態，並且可以輕鬆描述特定機器。“