turing-machines

如何找到升補， L = {<M>: M is a TM, which accepts some palindrome} 什麼是尋找一個補充的一般規則？我在這個特殊的情況下，以爲這將是 L_bar = {<M_bar> : M_bar is a TM, which rejects any palindrome .???

-1熱度

1回答

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

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

0熱度

1回答

可刪除性不可定義

我想問一下有關減少。在證明ETM是在M1的定義undecideable是 1.如果X！= W，拒絕 2.如果X = W，輸入運行男女並接受如果M確實在我遇到的很多證據中，我看到了粗線，但我不明白我該怎麼做，因爲我不知道它是否會停止。我會很高興知道我在哪裏錯了。謝謝。

0熱度

1回答

這種語言是否可確定

L = {（，，x）| M1（x）嚴格執行多於M2（x）的步數}。（如果兩個計算都是永久運行的，那麼兩個計算都不會比另一個嚴格得多）。該語言是否可判定？如何證明它？

0熱度

1回答

圖靈機：取兩個數字的mod？

設計一個圖靈機，它將輸入兩個非負數並對它們執行mod操作，例如mod（3,7）= 3和mod（7,3）= 1。顯然，指定關於TM的輸入和輸出的任何假設和格式。