كيفية إنشاء آلة تورينج تعمل كآلة حاسبة دالة لـ x^y

Question

أدرس لإجراء اختبار على آلات تورينج، وأنا عالق في مشكلة حيث يتعين علي إنشاء آلة تورينج تعمل كآلة حاسبة وظيفية من أجل:

f(x,y) = x ^ y 

أتفهم أن إدخال الشريط الخاص بي سيتم فصله على النحو التالي:

1's of base 0 1's of exponent 

مع أن يكون إخراج الشريط الخاص بي مثل

1's of base 0 1's of exponent 0 1's of the computed result

كيف يمكنني وضع علامات X وY على الشريط (الأشرطة)؟(يمكن أن تكون آلة متعددة الأشكال) كيف سيبدو مخطط الحالة؟

ملحوظة:أنا أستخدم الأحادي مع 1 يستخدم لتمثيل 0 و 0 لا يستخدم كقيمة بل كمحدد.

لذا:

   0 = delimiter
   1 =    0
   11 =   1
   111 =  2
   1111=  3
   11111= 4 
   etc.

Answer 1

أظن هنا بعض الشيء، لقد مر وقت طويل منذ أن لعبت مع محاكيات آلة تورينج.في البداية، أود تقسيم المهمة إلى عدة خطوات مفاهيمية:

1. زيادة رقم على الشريط بقيمة رقم آخر على الشريط
2. ضرب رقم على الشريط بقيمة رقم آخر على الشريط - يمكن القيام بذلك عن طريق تنفيذ الخطوة 1 بشكل متكرر
3. تربيع رقم على الشريط - x ^ 2 يتم حسابه عن طريق وضع x على الشريط ثم ضربه في نفسه
4. (الخطوة الأخيرة) رفع رقم على الشريط إلى قوة قيمة رقم آخر على الشريط - يمكن القيام بذلك عن طريق تنفيذ الخطوة 2 بشكل متكرر

لأداء مهمة بشكل متكرر N مرات، ضع N على الشريط، وقم بتنفيذ المهمة مرة واحدة، ثم اطرح 1 من نهاية الرقم N.كرر ذلك حتى يختفي الرقم N من الشريط.

نأمل أن يكون هذا كافيًا للبدء على أي حال.يمكن بناء آلة الدولة بشكل أو بآخر ميكانيكيًا بهذه الطريقة.

Answer 2

في كود تورينج الزائف الخاص بي:

1. انسخ الإدخال A0B إلى الشريط 2
2. اكتب 000010000 على الشريط 3
   • اضرب الرقم الموجود على الشريط 3 بـ A من الشريط 2 بـ
     1. ابتداء من بداية أ
     2. الكتابة 0 إلى الشريط 4
        • نسخ رقم 3 => 4
        • المضي قدمًا مرة واحدة على الشريط 3 (3++)
        • الذهاب إلى الخطوة 3 ما لم ينتهي
        • نقل الإجابة من الشريط 4 إلى الشريط 3
   • إنقاص الرقم B على الشريط 2
3. إذا لم تكن قيمة B الموجودة على الشريط 2 هي 0، فانتقل إلى الخطوة 2
4. انسخ الإجابة من الشريط 3 إلى الشريط 1

إليك رمز تورينج الذي يجب أن يعمل (الأشرطة تشبه المؤشرات، والأحرف الصغيرة، وشريط الإدخال هو i):

# At the start for 2^3
# i: 000111011110000
#       ^

_start_ -> *a = 0, start2
start2 [*i==0] -> i++, *a++ = 0, *b++ = 0, start4
start2 [*i==1] -> i++, *a++ = 1, start2
start4 [*i==0] -> *b-- = 0, b--, initc
start4 [*i==1] -> i++, *b++ = 1, start4
initc -> *c++ = 0, *c++ = 1, *c++ = 1, *c-- = 0, mult

# example
# i: 00011101111000
#              ^
# a: 001110000
#        ^
# b: 001111000
#         ^
# c: 00011000
#        ^

mult[*b==0]: lastcpy
mult[*b==1]: b--, *d++ = 0, *d++ = 1, rewa
rewa[*a==0]: a++, a++, multcpy
rewa[*a==1]: a--, rewa

multcpy[*c==1]: c++, multcpy2
multcpy[*c==0]: multcpy3
multcpy2[*a==0]: multcpy
multcpy2[*a==1]: *d++ = 1, multcpy2
multcpy3: *d-- = 0, *c = 0, cpydtoc

cpydtoc[*d==1]: d--, *c++ = 1, cpydtoc
cpydtoc[*d==0]: *c-- = 0, mult

lastcpy[*c==1]: *i++ = 1, c--, lastcpy
lastcpy[*c==0]: *i = 0, _finish_

# Should end with
# i: 00011101111011111111100
#                          ^

يرجى التحقق من الأخطاء :)