本頁只刊出中文翻譯與中文說明；英文原文請見下方原文連結。
原文連結
論文資訊
- 類型：已發表論文
- 日期：2022-09-02
摘要
我們考慮一種可以即時識別各種語言的模擬計算模型。我們透過組合迭代映射將輸入單字編碼為 R-d 中的點，然後將不等式應用於結果點以測試語言中的成員資格。每類映射和不等式（例如具有有理係數的二次函數）都能夠識別特定類別的語言。例如，線性和二次映射可以同時具有堆疊式和佇列式記憶體。我們使用相當於 Vapnik-Chervonenkis 維數的方法來將我們的一些類別彼此分開：線性映射不如二次或分段線性映射強大，多項式不如初等（三角和指數）映射強大，並且每個階數的確定性多項式不如其非確定性對應項強大。將這些動態類別與各種離散語言類別進行比較有助於闡明迭代映射如何在連續體中儲存和檢索資訊、計算在從符號序列到連續空間的編碼中可以隱藏的程度以及一般模擬和數位計算之間的關係。我們將該模型與其他模擬計算模型聯繫起來；特別是，它可以被視為 Blum、Shub 和 Smale 實值機器的即時、恆定空間、離線版本。 (C) 1998 年由 Elsevier Science B.V. 出版。保留所有權利。