واكا واكا! تلعب آلة تورينج هذه لعبة باك مان

عندما قرأت أحدث الأوراق حول الحوسبة القائمة على الحمض النووي ، كان علي أن أواجه حقيقة غير سارة إلى حد ما. على الرغم من أنني متخصص في علم الوراثة وتخصص أيضًا في علوم الكمبيوتر ، إلا أنني كنت أعاني من أجل ربط مفهومين – آلة تورنج العالمية ، وجوهر الحوسبة ، وبنية فون نيومان ، وهي أساس معظم وحدات المعالجة المركزية الحديثة. كنت قد كتبت كود C ++ لمحاكاة الآلة الموصوفة في ورقة تورينج عام 1936 ، ويمكنني استخدامها لتقرير ، على سبيل المثال ، ما إذا كانت الكلمة متناظرة. لكن لم أستطع رؤية كيف يمكن لمثل هذه الآلة – بذاكرة الشريط أحادية البعد والقدرة على النظر إلى رمز واحد فقط على هذا الشريط في كل مرة – أن تتصرف مثل معالج مليار ترانزستور مع ميزات الأجهزة مثل وحدة المنطق الحسابي (ALU) ، عداد البرامج ، وسجل التعليمات.

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

بدلاً من عملاق مليار ترانزستور ، اعتقدت أنني سأستهدف المعالج الصغير 6502 8 بت المتواضع. كانت هذه الرقاقة الأسطورية تعمل على تشغيل أجهزة الكمبيوتر التي استخدمتها في شبابي. وكدليل نهائي ، يجب أن يعمل معالج المحاكاة الخاص بي باك مانوتحديداً إصدار اللعبة المكتوب لجهاز كمبيوتر Apple II.

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

كان الكشف الرئيسي بالنسبة لي هو أن السجلات الداخلية لـ 6502 يمكن تكرارها بالتسلسل على المفكرة أحادية البعد باستخدام أربعة رموز – 0 ، 1 ، _ (أو مسافة) ، و $. يتم استخدام الرموز 0 و 1 لتخزين البيانات الثنائية الفعلية التي يمكن وضعها في سجل 6502. يُستخدم الرمز $ لتحديد السجلات المختلفة ، ويعمل الرمز _ كعلامة ، مما يجعل من السهل العودة إلى مكان في الذاكرة نعمل معه. يتم محاكاة الذاكرة الرئيسية لـ Apple II بطريقة مماثلة.

بصرف النظر عن بعض flip-flops ، وبوابتان NOT ، وعداد لأعلى لأسفل ، فإن آلة PureTuring تستخدم فقط رقاقات RAM و ROM – لا توجد شرائح منطقية. لوحة اردوينو [bottom] يراقب ذاكرة الوصول العشوائي لاستخراج بيانات العرض. جيمس بروفوست

تتعلق برمجة وحدة المعالجة المركزية بمعالجة السجلات ونقل محتوياتها من الذاكرة الرئيسية وإليها باستخدام مجموعة التعليمات. يمكنني محاكاة تعليمات 6502 كسلسلة من القواعد التي عملت على السجلات ، رمزًا برمز. يتم تخزين القواعد في ذاكرة القراءة فقط (ROM) القابلة للبرمجة ، مع إخراج قاعدة واحدة تملي القاعدة التالية لاستخدامها ، وما يجب كتابته على المفكرة (يتم تنفيذه كشريحة ذاكرة الوصول العشوائي) ، وما إذا كان ينبغي قراءة الرمز التالي أم الرمز السابق .

لقد أطلقت على جهازي PureTuring. ترتبط مخرجات بيانات ROM بمجموعة من flip-flops. يتم توصيل بعض flip-flops بذاكرة الوصول العشوائي ، للسماح بإحضار الرمز التالي أو السابق. يتم توصيل الآخرين بخطوط العنوان الخاصة بـ ROM في حلقة ملاحظات تحدد القاعدة التالية.

اتضح أنه من الأكثر كفاءة تشذير أجزاء من بعض السجلات بدلاً من تركها على هيئة قطع 8 بت منفصلة. يتطلب إنشاء كتاب القواعد لتنفيذ مجموعة تعليمات 6502 9000 قاعدة. من بين هؤلاء ، تم إنشاء 2500 باستخدام طريقة المدرسة القديمة لكتابتها على بطاقات الفهرسة ، وتم إنشاء الباقي بواسطة برنامج نصي. استغرق وضع هذا معًا حوالي ستة أشهر.

يتعرض المبرمجون فقط لبعض السجلات البالغ عددها 6502 [green]؛ سجلاتها الداخلية المخفية [purple] تستخدم لتنفيذ التعليمات. أسفل كل سجل كيفية ترتيب السجلات ، وأحيانًا يتم تشذيرها ، على “شريط” PureTuring.جيمس بروفوست

لجلب تعليمات البرنامج ، تخطو PureTuring عبر المفكرة باستخدام رموز $ كمعالم حتى تصل إلى موقع الذاكرة المشار إليه بواسطة عداد البرنامج. يبلغ طول أكواد التشغيل 6502 بايت واحد ، لذا بحلول الوقت الذي تتم فيه قراءة البتة الثامنة ، يكون PureTuring في واحدة من 256 حالة. ثم يعود PureTuring إلى سجل التعليمات ويكتب كود التشغيل هناك ، قبل الانتقال لتنفيذ التعليمات. يمكن أن يستغرق الأمر ما يصل إلى 3 ملايين دورة ساعة PureTuring للجلب ، مقابل دورة واحدة إلى ست دورات لـ 6502 الفعلية!

يستخدم 6502 نظام إدخال / إخراج معين للذاكرة. هذا يعني أن الأجهزة مثل شاشات العرض يتم تمثيلها كمواقع في مكان ما داخل الذاكرة الرئيسية. باستخدام Arduino لمراقبة جزء المفكرة الذي يتوافق مع ذاكرة رسومات Apple II ، يمكنني استخراج وحدات البكسل وعرضها على محطة أو شاشة متصلة. يتطلب هذا كتابة وظيفة “إزالة الأوزان” لـ Arduino حيث يتم وضع بيانات بكسل Apple II في مخطط معقد. (أنشأ Steve Wozniak هذا المخطط لتمكين Apple II من تزييف إشارة تلفزيونية ملونة تناظرية باستخدام رقائق رقمية والحفاظ على تحديث ذاكرة الوصول العشوائي الديناميكية.)

كان بإمكاني إدخال مدخلات من لوحة مفاتيح في المفكرة بطريقة مماثلة ، لكنني لم أزعج نفسي لأنني ألعب بالفعل
باك مان على PureTuring يتطلب صبرًا غير عادي: استغرق الأمر حوالي 60 ساعة فقط لرسم قيمة حركة إطار واحد باك مان الشخصية ومطاردة أشباح العدو. أضاف التعديل الذي نقل الجهاز على طول السلسلة المتصلة نحو بنية فون نيومان دوائر للسماح بالوصول العشوائي إلى رمز المفكرة ، مما يجعل من غير الضروري المرور عبر جميع الرموز السابقة. قطع هذا التعديل الوقت لرسم شخصيات اللعبة إلى 20 ثانية فقط لكل إطار!

https://www.youtube.com/watch؟v=7hP4BTWvrGwPureTuring الجزء 1. معالج دقيق لآلة تورينج.www.youtube.com

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

الآن عندما أقرأ الأوراق والمقالات حول الحوسبة القائمة على الحمض النووي ، يمكنني تتبع كل عنصر إلى شيء ما في آلة تورينج أو الانتقال إلى بنية تقليدية ، وتشغيل الآلة العقلية الصغيرة الخاصة بي على طول شريط مفاهيمي!