遞歸可判定語言，接受無限語言

Question

所以我的理解是遞歸可Decidable語言是我們可以構建一個圖靈機的語言，因此如果從該語言輸入w，圖靈機將始終接受並暫停或拒絕並停下來。我感到困惑的是可以長到無限的語言。舉個例子，我們有一個語言L = {0^p | p是素數}。所以我們可以編寫一個算法來確定一個數是否是線性空間中的素數。所以我的理解是，既然這個算法或者告訴我們數字是素數或者不是素數，那麼L必須是遞歸可判定的嗎？但是由於p不受任何固定數量的限制，它可以正確無限？那麼，假設我的算法可以在技術上永遠運行而不接受或拒絕輸入，那麼是否正確？在這種情況下，我們的L不會遞歸地確定並遞歸枚舉？

Answer 1

1. 是的，黃金長度的一元單詞的語言是可判定的。正如你所說，這甚至可以在輸入大小的線性空間中完成。
2. 是的，該語言包含任意長度的單詞。但說p走向無窮是誤導。它採用所有可能的整數值，但沒有任何順序。無窮大不是一個整數，因爲在集合定義中沒有秩序，所以沒有任何走向無窮的趨勢。
3. 不，你不能假設算法永遠運行。它不會將所有字符串作爲輸入，而只是一個。並且每一個字符串都是有限長度的，所以算法將終止它們中的每一個。無限多種可能的輸入這一事實在這裏並不重要。