圖靈機接受總理長度

我有一個要求我描述了接受L = {a^n: n is prime}非確定性圖靈機程序的功課問題的字符串。我不確定如何去做這件事。我知道嗎？我是否使用a作爲一元數字並對它們進行計數？我可以忽略這個字符串，只是測試主要的n？或者是已知的主要值，因此只有那些單元格位置才能接受狀態，並且我可以像正常一樣讀取數據？圖靈機接受總理長度

我該怎麼辦？

來源

2012-04-12 calccrypto

你應該請你的講師或導師澄清。我們可以嘗試猜出它們的含義（不管這種猜測是否聰明），但只有他們知道。 – paxdiablo 2012-04-12 01:13:35

如果你的標題去的話，大概是什麼的意思是，你的NTM應該接受最佳長度的'a's任何字符串。所以計算你的'a'，如果看到任何其他符號，並且沒有更多符號時，拒絕字符串，如果計數是質數，則接受。看起來像。當然，沒有素數是「已知的」，你的磁帶最初只包含一系列'a's，其餘的都是空白的。 – 2012-04-12 08:07:20

上http://programmers.stackexchange.com/ – Abizern 2012-09-23 20:25:48

你可以把埃拉托色尼的實際無限篩到您的原點的左側，在磁帶上。

不確定性，您可以爲每個國家一個以上的轉換規則。所以，當以n的增量進行離開時，您可以在每個點上a。繼續向左走並以n爲增量標記磁帶;或b。從原點開始，下一個n。

然後讓你的起始狀態有兩條規則（也許在檢查完磁帶上的所有內容都只有a s並且沒有別的）：a。開始標記2的倍數，並且b。（現在假設篩子已經到位）計算您的a s並使用原點左側的標記素數來決定是否接受。

因此，您的最初磁帶，........aaaaaaa.........將最終變得像.c.ccccc.ccc.c.ccc.c.ccc[p]cpcpp.OaaaaaaaA...x.y.z...（與[]標記磁帶上的最終頭部位置）。

來源

2012-04-12 12:03:21

首先，你可以使用一個內存位置的某處以字符串標誌是否已被發現是最佳長度與否，然後做更多或更少內斯建議是什麼（雖然我真的不明白他的回答的全部）。

使用埃拉托色尼的篩。以長度爲2的輔助字符串開始，並在輸入字符串和輔助字符串中向右移動一個，當您點擊助手字符串的結尾字符時，返回輔助字符串的開頭，直到您敲擊輸入的結尾字符串。通過這種方式，您可以查看幫助程序字符串是否將輸入字符串分開。然後轉到長度爲3的輔助字符串並執行相同的操作，依此類推。只有當輔助字符串長度沒有區分輸入字符串長度時，纔是輸入字符串長度素數。如果一個輔助字符串長度將輸入字符串長度分開，請使用標誌內存插槽來顯示該長度。並且讓算法檢查標記內存插槽，如果它被標記，則放棄所有處理，以便可以拒絕該字符串。

現在，在任何點處，同時遍歷輸入允許非確定性跳出內循環使機器可以開始測試下一長度的輔助串。這樣，從某種意義上說，所有長度的幫助字符串都將被同時測試，但是當您的標誌位被標記時，它們將停止處理並拒絕字符串。

最後一個問題。字符串可能在之前被接受（儘管時間在這裏是一種非概念），但它們被發現是非素數。如果你能弄清楚這個問題，你比我早一步。

P.S. Drineas是邪惡的

來源

2012-04-12 19:08:29 Outback

圖靈機接受總理長度

回答

相關問題