decidable

-1熱度

1回答

我不知道如何開始。我的想法是從一些NP完全問題提供多時間減少。 E_tm 我不明白的是，知道E_tm不可判定，但NP-Hard類是可判定的。

-1熱度

1回答

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

0熱度

1回答

可判定語言（計算模型）

我需要證明L是否可判定與否： L = {< M> | M是TM和L的（M）的結合和對H_TM是在RE} （H_TM = {< M，W> | M是上瓦特}停止一個TM）

1熱度

1回答

我們可以決定一個數n是否屬於一個可數集S？

現在的問題如下：設S是N（自然數）的一個子集，所以它是無限且可數的。讓Ls = {a^n | n屬於一種語言。是遞歸的？ Ls是遞歸枚舉？證明你的答案。我很確定Ls對任何S都是遞歸的，因爲我們可以編寫一個決定Ls（或者Turing Machine）的程序。但我如何證明它呢？

3熱度

4回答

爲什麼OWL完全不可判定？

我一直在四處尋找一切爲什麼OWL完全是不可判定的，但我還沒有找到一個容易理解的例子，這將導致我理解它。我發現瞭解釋這是由於「Entailment Closure」的說法，這也與OWL Full可以具有屬性的類以及同時也是個人的事實相關。但是我不理解那些語句之間的關係。

5熱度

1回答

證明這個語言是否可判定和識別

如果L1和L2語言中，我們有一個新的語言 INTERLACE(L1, L2) = {w1v1w2v2 . . . wnvn | w1w2 . . . wn ∈ L1, v1v2 . . . vn ∈ L2}. 例如，如果abc ∈ L1和123 ∈ L2，然後a1b2c3 ∈ INTERLACE(L1, L2) 我怎麼能證明INTERLACE是： decidable？可識別？我知道如何顯示

1熱度

1回答

檢查是否2種語言的圖靈識別或共同圖靈識別

我有這2種語言 A = {<M> | M is a TM and L(M) contains exactly n strings } B = {<N> | N is a TM and L(N) contains more than n strings } 我相信，這些2是不可判定的，但我不知道他們是否圖靈識別或共同圖靈識別。

0熱度

1回答

什麼是圖靈機正在停擺？

我是新的可判定性。我讀過停止問題，但沒有得到任何實際上暗示的東西。我已經搞砸了解釋。任何人都可以提供我任何聲音的解釋或至少一些細節，這將有很大的幫助？

0熱度

1回答

無法爲可判定語言創建算法

L2 = {<M> : M is a TM and there exists an input string w such that M halts within 10 steps on input w} 嗨。我正在創建一個算法，以顯示L2以上是可確定的。而提示被給出爲以下：要顯示L2是可判定的，測試對長度的所有輸入串給定的TM M達至多10，每一個用於10個步驟。請注意，有很多這樣的字

1熱度

1回答

具有決定器決定{<M> | M是TM和| L（M）| = N}，建立一個判定器判定N-1

這是可能的？假設我們有一個決定器決定{| M是一個TM和| L（M）| = N} 要建立一個決定器決定{| M是一個TM和| L（M）| = N-1} 如果可能的話，如何？