تصميم طاولة حالة آلة تورينج

Question

هل هي أي إرشادات مفيدة لوصف ما تفعله آلة تورينج إذا كان لديك بالفعل رمز الزائفة للخوارزمية؟

أنا آخذ دورة حول نظرية التعقيد ويستغرق الأمر بعض الوقت لوصف آلة تورينج التي تقرر أو تقبل بعض اللغة (الحالات ، التحولات ، وما إلى ذلك) على الرغم من أنني أعرف كيف يمكنني ترميزها في شيء مثل C أو حتى التجميع . أعتقد أنني لم أمتلك ما يكفي من الممارسة مع آلات Turing (العمل عليها) ، لكنني أقدر أي اقتراحات.

تعديل

لا أريد أن أجعل جهاز محاكاة لآلة Turing ، أريد أن أصف آلة تورينج على الورق (الأبجدية ، الحالات ، التحولات) لتحديد بعض اللغة.

إليك مثال تافهة لما أعنيه ، قل أنني بحاجة إلى كتابة آلة تورينج تتجاوز سلسلة من 0S و 1s وتغيير جميع 0s في 1s. على سبيل المثال ، إذا بدأت بـ 11010 على الشريط (الإدخال) ، فإنه يتوقف مع 11111 على الشريط (الإخراج). الآن بلغة عالية المستوى تعرف أنها شيء مثل:

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

وصف آلة تورينج شيء غير رسمي مثل:

لديك دولتان ، س ووقف. عندما تكون في حالة Q وترى 1 ، انتقل إلى اليمين دون تغييره. إذا رأيت 0 ، قم بتغييره إلى 1 وانتقل إلى اليمين. إذا رأيت الرمز الفارغ (نهاية الشريط) ، فانتقل إلى حالة التوقف.

رسميًا سيكون لديك شيء مثل {Q ، HALT} للحالات. {((q ، 1) -> (q ، 1 ، r)) ، ((q ، 0) -> (q ، 1 ، r)) ، ((q ، #) -> (HALT ، 0 ، L) )} للتحولات.

الآن هذه المشكلة تافهة ، ولكن هناك آخرون يشملون أكثر (إضافة أرقام أحادية أو التعرف على لغة ذات عدد متساوٍ من A و B's و C's). كان بإمكاني كتابة الرمز الكاذب بسهولة لهم ، لكن كتابة آلة تورينج أكثر صعوبة بكثير (تأخذني وقتًا طويلاً) وكنت أتساءل عما إذا كانت هناك بعض النصائح أو الموارد أو الإرشادات التي تساعدني على أن أصبح أفضل في حل المشكلات مثل ذلك.

Answer 1

عدم اعطاء رأي: سؤالك عام للغاية ، وبالتالي فهو هذا الإجابة. لاحظ أنني غير خبير في TMS ، ولن يكون هذا النهج فعالًا للغاية (لا يمكنني حتى أن أعد أنه سيكون فعالًا دائمًا). أنا فقط أخرج بعض الأفكار هنا.

أود أن أقترح تجربة مثل هذا النهج: خذ رمزك الزائف وقم بتقليله بحيث يتكون فقط من أ) متغيرات منطقية و ب) 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

عندما تكون متداخل ifS ، استبدلهم بـ andس؛ إزالة else كتل باستخدام not:

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 شروط مثل كل واحد على حده من المنطقي الخاص بك والرسالة الحالية يتم فحصها دائمًا ، مما يكرر الكتل حيث تكون ضرورية. مثال:

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

# ...

هذه القيمة العددية لـ Bitfield هي حالة Turing Machine. ال do_a الجزء هو مجرد مهمة لـ Booleans (أي The Bitfield ، لذلك هي حالتك الجديدة) ، وأمر الكتابة (إذا لم يكن هناك ، فقط اكتب الرسالة التي كانت موجودة بالفعل) وأمر حركة ، وبالتالي عملية انتقال صريح.

آمل أن يكون أي مما سبق منطقيًا.

Answer 2

هل تحتاج إلى أداة جاهزة للاستخدام ، Turing Machine Simulator؟ هناك العديد من المتاحة. أو في الواقع تريد أن تصنع بنفسك؟ يبدو أن هذا تطبيق صالح في JavaScript: http://klickfamily.com/david/school/cis119/turingsim.html يمكنك تحليل الكود وترجمته إلى C أو C ++ بسهولة تامة.