computability

0熱度

1回答

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

1熱度

1回答

測量位序列複雜度的方法

我正在尋找一種簡單的方法來估計一個固定大小（可能是最大長度爲10）的位序列的複雜性。例如，我想0000000和111111根本不是很複雜，但101010和101101位於頻譜的其他地方。我知道Kolmogorov的複雜性是不可計算的，但它是否可以用二進制字母表對固定（和小）長度的序列進行簡單編程？還是有另一種措施可能只是近似的措施，但更容易計算？該措施非常簡單，以便我可以向其他（儘管受過良好教

1熱度

2回答

子集大小爲'k`的子集合是NPC嗎？

我有一個Subset-Sum problem的變化，其中子集的大小是k，並且所有整數都是正數（而非零）。從網上可以看出，這個問題可以用僞多項式時間的動態規劃來解決。我需要決定這個問題是NPC，還是在P（同時假設P!=NP）。我試圖減少子集和問題，但有一個約束，所有整數必須大於零的問題。除此之外，我會用k填充零輸入。問題的正式定義： L={<S1,S2,...,Sn,T,k>|There e

-2熱度

1回答

證明常規語言和上下文無關語言是遞歸的

我對常規語言和上下文無關語言之間的區別有點困惑。遞歸語言是一種語言，爲此它退出一直停止的TM。我在證明上述說法時遇到問題。

0熱度

1回答

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

我想知道上面這個聲明[標題]是否屬實。這是我已經有：非遞歸意味着不可判定。我讀過這個 Are all infinite languages undecidable? 它說：如果語言是不可判定（非遞歸），必須有一些字符串使TM未能halt.SO它必須具有無限他們使TM失敗的原因。這怎麼能證明我的陳述[標題]？任何人都可以更清楚地向我解釋一下嗎？謝謝 ps。對困惑感到抱歉。是TM意味着圖靈

0熱度

1回答

減少功能是否對應？

我正在學習可編程性和複雜性，並且我懷疑是否有問題。將問題減少到另一個問題的函數是圖靈算法。我想知道是否它甚至是一個一對一的函數（對應），例如，查看頂點覆蓋 - >獨立集減法，我看不到一個問題的實例不與另一個實例相對應另一個。謝謝

16熱度

4回答

是否有黑盒方法來檢測排序算法是否穩定？

在JavaScript中（某種程度上適用於其他地方），您不知道代碼在哪個目標上運行，是否有一種方法可以檢測底層排序算法（Array.sort）是否穩定，只知道它如下the specification？我可以在webkit (1)(2)中找到2個測試，但這些測試有多可靠？（可以用PCP來完成這項檢查嗎？）我正在尋找一種數學上可行的解決方案。這是一個棘手的問題，因爲更高級的排序算法可以根據源數組

6熱度

4回答

無限語言不能定期？什麼是有限語言？

我在一本書上可計算閱讀：（克林定理）語言是正則的當且僅當它可以通過應用三個操作結合，串聯，重複有限，從有限的語言獲得次數。我很苦惱「有限的語言」。考慮這樣的語言：L = a* 這是不是有限的。它是集合{0, a, aa, aaa, ...}，這顯然是一個無限集合（0 =空字符串）。所以這是一種無限的語言，對吧？也就是說，「無限集合」的意思是「無限語言」，對吧？顯然，a*是一種常規語言

7熱度

2回答

修改後的Brainfuck版本的圖靈完備性

是Brainfuck圖靈完成如果單元是位，並且+和 - 操作簡單地翻轉一點？是否有一個簡單的證據表明Brainfuck-like語言不管單元大小如何都是圖靈完成的，還是我需要考慮一個模擬圖靈機的程序？我怎麼知道如果沒有一個？編輯：我找到了我的問題的答案：Brainfuck與位單元被稱爲Boolfuck。普通的Brainfuck可以減少到它，所以Boolfuck是圖靈完整的。

1熱度

4回答

理解正式語言中的Σ*和Σ

如果我有Σ={a}，Σ*有什麼詞？ Σ*= {a,aa,aaa,aaaa.....}？感謝