證明所有非遞歸語言都是無限的

我想知道上面這個聲明[標題]是否屬實。證明所有非遞歸語言都是無限的

這是我已經有：非遞歸意味着不可判定。

它說：

如果語言是不可判定（非遞歸），必須有一些字符串使TM未能halt.SO它必須具有無限他們使TM失敗的原因。

這怎麼能證明我的陳述[標題]？任何人都可以更清楚地向我解釋一下嗎？

謝謝

ps。對困惑感到抱歉。是TM意味着圖靈機。太清楚了我的問題是：所有非遞歸語言都是無限的嗎？

2013-11-20 geasssos

你似乎在這裏有許多不同的概念。你是否想知道「非遞歸==無限」還是「非遞歸==不可判定」或「無限==不可判定」或其他什麼東西？另外，不要使用人們不太可能理解的縮寫（儘管我猜測「TM」意思是「圖靈機」，至少基於問題領域）。 – twalberg

抱歉的困惑。是TM意味着圖靈機。太清楚了我的問題是：所有非遞歸語言都是無限的嗎？ @twalberg – geasssos

考慮一種由單個字符（稱爲A）和單個產品「P - > A」組成的字母表。該語言接受單個輸入，即A，並且絕對不是遞歸的，並且絕對是非無限的。所以，不，並非所有的非遞歸語言都是無限的...... – twalberg

作爲提示：證明所有有限的語言都是規則的。所有正規語言都是可確定的。考慮到這個陳述的對立，你會發現所有不可判定（非遞歸）的語言都是無限的。

希望這會有所幫助！

2013-11-20 18:16:53 templatetypedef

回答