設計一個圖靈機的狀態表

如果你已經有了算法的僞代碼，它們是否有用來描述圖靈機做什麼的有用指導？設計一個圖靈機的狀態表

我正在學習複雜性理論課程，它花了我一段時間來描述決定或接受某種語言（狀態，轉換等）的圖靈機，即使我知道如何在類似的東西C甚至組裝。我想我只是沒有足夠的練習圖靈機（工作），但我很欣賞任何建議。

編輯

我不想做一個圖靈機模擬器，我想描述在紙上（字母，狀態，轉換）圖靈機來決定一些語言。

下面是我的意思的一個簡單例子，比如說我需要編寫一個圖靈機，它會遍歷0和1的字符串，並將其中的所有0都更改爲1。例如，如果您在磁帶（輸入）上以11010開頭，則它會在磁帶（輸出）上以11111結束。現在，在一個高層次的語言，你知道它是這樣的：

Go over every character on tape 
    If character is 0 change it to 1

圖靈機的描述是非正式一樣的東西：

你有兩種狀態，q和停止。當處於狀態q並且您看到1時，可以在不改變它的情況下向右轉到。如果您看到一個0，請將其更改爲1並轉至右側。如果看到空白符號（磁帶結束），則轉到停止狀態。

正式的，你會有類似{q，halt}的狀態。（（q，1） - >（q，1，R）），（（q，0） - > ）}進行轉換。

現在這個問題是微不足道的，但也有其他更涉及（增加一元數字或識別語言數量相同的a，b和c的數量）。我可以很容易地爲他們編寫僞代碼，但是編寫圖靈機要困難得多（需要很長時間），我想知道是否有一些技巧，資源或準則可以幫助我更好地解決這類問題。

來源

2010-01-20 Firas Assaad

你是什麼意思「構建語言的圖靈機」？ – balpha 2010-01-20 07:28:09

你需要將手放在無限長的磁帶上。 – 2010-01-20 07:32:01

@balpha：通常我會遇到像「提出決定語言{w屬於{a，b} *：w至少包含一個a}的語言的圖靈機」。只是我書中的一個隨機例子。我重新提出了我的問題，使其更清楚。 – 2010-01-20 07:33:19

免責聲明：您的問題是非常普遍的，因此這個答案也是如此。請注意，我什麼都不是TM的專家，而且這種方法通常效率不高（我甚至不能保證它總是有效）。我只是在這裏記下一些想法。

我會建議嘗試這樣的方法：拿你的僞代碼，並減少它，使它只包含一個）布爾變量和b）if-陳述。例如：

if THIS_LETTER_IS("A"): 
    found_an_even_number_of_A = not found_an_even_number_of_A 

if THIS_LETTER_IS("Q") and previous_letter_was_X and found_an_even_number_of_A 
     and not checking_for_alternative_2: 
    # can't be a word of alternative 1, so check for alternative 2 
    going_back_to_start_to_check_for_alternative_2 = True 

if going_back_to_start_to_check_for_alternative_2: 
    MOVE_TO_PREVIOUS 
else: 
    MOVE_TO_NEXT 

if going_back_to_start_to_check_for_alternative_2 and THIS_LETTER_IS(EMPTY): 
    # reached the beginning, so let's check for alternative 2 
    going_back_to_start_to_check_for_alternative_2 = False 
    checking_for_alternative_2 = True

當你嵌套if年代，隨着and小號取代它們;通過使用not除去else塊：

if something: 
    if something_else: 
     do_a 
    else: 
     do_b

變得

if something and something_else: 
    do_a 

if something and not something_else: 
    do_b

然後每個if塊應該只包含一個MOVE_TO_PREVIOUS或MOVE_TO_NEXT，可能是WRITE命令和變量賦值的任何數目。

完成所有if條款，使得每一個你的布爾值和當前信的一個始終檢查，重複塊，其中neccessary。例如：

if something and something_else: 
    do_a

成爲

if THIS_LETTER_IS("A") and something and something_else and something_i_dont_care_about_here: 
    do_a 

if THIS_LETTER_IS("A") and something and something_else and not something_i_dont_care_about_here: 
    do_a 

if THIS_LETTER_IS("Q") and something and something_else and something_i_dont_care_about_here: 
    do_a 

if THIS_LETTER_IS("Q") and something and something_else and not something_i_dont_care_about_here: 
    do_a

現在，如果你有ñ布爾和米信，你應該有米 * 2 ^ňif秒。想象一下，您已將布爾值存儲在一個位域中，因此每個可能的布爾值組合代表一個整數。因此上述變

if THIS_LETTER_IS("A") and bitfield[0] and bitfield[1] and bitfield[2]: 
    do_a 

if THIS_LETTER_IS("A") and bitfield[0] and bitfield[1] and not bitfield[2]: 
    do_a 

# ...

然後成爲

if THIS_LETTER_IS("A") and bitfield == 7: 
    do_a 

if THIS_LETTER_IS("A") and bitfield == 3: 
    do_a 

# ...

這對位域的整數值是圖靈機狀態。 do_a部分只是一個布爾值賦值（即位域，所以它是你的新狀態），一個寫命令（如果沒有的話，只寫一個已經是的字母）和一個移動命令，因此顯式地是一個圖靈機過渡。

我希望以上任何一條都有道理。

來源

2010-01-20 09:18:56 balpha

這正是我們所需要的。我在問，謝謝！ – 2010-01-20 09:23:23

您是否需要現成的工具Turing Machine模擬器？有quite many available。或者實際上你想製作你自己的？這似乎是JavaScript中的一個有效實現：http://klickfamily.com/david/school/cis119/TuringSim.html您可以分析代碼並將其很容易地轉換爲C或C++。

來源

2010-01-20 07:34:03 naivists

我不想製作一個圖靈機模擬器，我如果我沒有清楚地說出我的問題，我很抱歉，那些模擬器似乎對實驗非常有用 – 2010-01-20 07:38:10

設計一個圖靈機的狀態表

回答

相關問題