هاسكل بالعربي – الجزء التاني

البوست ده عن Automata Theory كمقدمة Formal لل Functional Programming , مش مرتبط 100% بالكودنج, لكن ده الاساس الرياضي الصحيح للتفكير بالطريقة المطلوبة للFP

———————

في وقت ما حوالين الثلاثينات من القرن الماضي كان فيه شوية علماء رياضيات و مهندسين و علماء احياء و علم نفس و كام واحد هيبقوا بعدين علماء في الكمبيوتر ساينس , اتجمعوا بشكل ما عشان يوصلوا لحاجة مهمة جدا, الا و هي, ازاي نعمل نموذج للعقل البشري و طريقة تفكيره, سواء بشكل رياضي او ميكانيكي او بطاطساية حتي مش فارقة, و قعدوا يدرسوا سوا كده الامور رايحة فين و جاية منين.

لحد ما في 1943 , طلع 2 محترمين كده دكاترة اصلا , تحديدا دكاترة في علم الاعصاب, و طلعوا ورقة بحثية مشهورة جدا ب-أسم “A Logical Calculus Immanent in Nervous Activity” و دي كانت بداية ظهور الNeural Networks , ك-نموذج للComputation عن طريق عمل نموذج رياضي للدماغ او تحديدا للعصبونات, و ازاي بتتفاعل مع بعضها, و من ده ظهر اول بدايات ال Automata Theory , اللي هي النظرية المختصة بتصميم و نمذجة الالات اللي بتعمل عمليات حوسبية/منطقية او Computational Machines و متخصصة كمان في تحديد هل المشكلة تنفع تتحل بشكل حوسبي (يعني تتحول لخطوات ينفع تكرارها) أو ﻷ مينفعش (كل ده عمله دكاترة يا جماعة لو تلاحظوا)

بعدهم جه اشهر 2 بني ادمين نعرفهم في الAutomata كلها G.H. Mealy and E.F. Moore خدوا الشغل بتاع الاخوة المحترمين اللي فوق و عملوله نوع من ال generalization , ليتحول لحاجة مشهورة جدا في الكمبيوتر ساينس الا و هي ال Finite State Machines , دي الالات الحوسبية الجميلة الل بتقدر تعمل وصف رياضي ﻷي عملية حسابية من عمليات تكرارية حالاتها محدودة , وظهر عندك ال Moore Machine و ال Mealy Machine , كنموذجين للكمبيوترات البسيطة دي – والفرق بينهم طريقة تعاملهم مع الStates (يعني ايه states ؟ هنعرف)

———————

بس ثواني, هو ايه اصلا الAutomata و النظرية بتاعتها؟ 
(تحذير محتوي رياضي)

بيقولك الAutomata دي, جمع كلمة automaton يعني شئ ما بيحرك نفسه بنفسه, او autonomous يعني, و في المعني الرياضي بتعني Abstract Machine قادرة علي اجراء عمليات منطقية بشكل ممنهج و محسوب, و فيه انواع كتير من الMachines دي (كلمة ماشين كانت بستعمل زمان للدلالة علي الحسابات المنطقية ﻷن الاخوة الاوائل اللي عملوا الكمبيوترات كانوا مهندسين ميكانيكا ثم بعدها مهندسين كهربا) – النظرية دي فيما بعد بقت جوهرة الكمبيوتر ساينس , ﻷن منها تفرع نظرية لغات البرمجة Language Theory و تمت استعارة اجزاء منها في نظم التحكم للانظمة الDiscrete و كمان بسببها قدرنا نربط بين الكمبيوتر ساينس و اي مجال في الكوكب و ظهر Computational Finance, Computation Biology, Computational Chemistry, Computational Linguistics و كمان وجود النظرية دي ساعد علي ظهور نظم الاتصالات و نظرية الاتصالات بشكلها الحالي و غيره من العلوم اللي بقي ممكن استعمال الكمبيوترات فيها بكفاءة و وصف رياضي محترم , بسبب مبادئ الاوتوماتا 🙂

فيه بقي جوا الاوتوماتا حاجات كتير لا يتسع البوست ليها, لكن اشهر المجالات الفرعية ليها :
Finite State Machines 
Pushdown Automata
Linear Bounded Automata 
Turing Machines
اللي موازي ليها Lambda Calculus بس اللامبدا لغة برمجة مش مكنة (و هنتكلم ازاي هما نفس الحاجة بالطريقة دي)

دول احد اشهر الانواع (و تاريخيا شوية تطورات) نظرية الاوتوماتا , من اول الالة اللي بتحسب حاجات معروفة و دقيقة, لحد الات اللي بتحسب اي حاجة ينفع تتحسب 🙂

———————

بعيدا عن كلام الهجايص اللي فوق, ازاي بقي رياضيا بعبر عن الكلام ده؟ 
اول حاجة عندنا شئ اسمه ال alphabet و دي ببتعرف انها :
non-empty set of symbols ,
يعني فئة – مينفعش تكون فاضية, فيها شوية رموز, الرموز دي هي المسموحة للتعبير عن النظام بتاعنا, زي في ال DNA موجود AGCT و في الانجليش ال26 حرف, و في النظام البيناري 1 و 0 , و غيره و غيره (يعني لو عرفت الalphabet بتاعة اي حاجة, اقدر اشتغل بيها في شكل رياضي؟ ايوة)

تاني حاجة عندنا شئ اسمه Stringو ده بقي ترتيب او مجموعة combinations من ال symbols اللي متاحة لينا في الalphabet , زي في ال DNA برضه, ِAGCTTTCCCGGAAT او في اللغة Hello او ارقام 10101010 او غيره.

تالت حاجة عندي Language , يعني المجموعة المسموحة من الStrings اللي ينفع اشتغل بيها (زي فيه اشكال DNA مسموحة او ﻷ, فيه كلمات منطقية و كلمات اي حاجة و غيره و غيره)

رابع حاجة, جوا الautomaton بتاعي, عندي اوقات بيظهر فيها symbols معينة او غيره, و اوقات حاجات تانية, اللحظة او الوقت اللي السيستم بيكون فيه في شكل معينة, ده اسمه State
لو انت في النظام بتاع الترقيم, فال 1 ده state عالnumber line , و2 ده state تانية و غيره

خامس حاجة, عندنا دايما transition function, بتقولنا ازاي بنتحرك بين الStates و بعضها, و ايه القواعد المسموحة للحركة دي جوا السيستم , و ساعات بيكون عندنا دوال تانية زي ال output function مثلا

بتجميعة ما مختلفة من الحاجات اللي فوق دي, بيتجمعوا سوا في نوع من الsets اسمها الtuple 
بتكون مجمعة كل ده في نظام رياضي جميل.

———————

تعالي ناخد ده خطوة لقدام, ونتكلم عن ازاي ممكن نوصف لو عندك سيستم بسيط زي الatm او الطلبات في المطعم او غيره , و يتعمله سيستم automaton صغير نقدر نعبر عنه رياضيا 
اول حاجة النظم اللي زي الatm او الغسالة او التلفيزيون او الطلبات في المطعم, دي جزء صغير من الانظمة بتاعة الكمبيوترات فيها عدد الstates محدود او finite, معروف اخره فين, لو عملت ايه مستحيل تعمل combination من الحالات برا اللي معمول في الوصف بتاعنا و دي اللي طلعلها بعد كده الاسم الروش جدا Finite-State Machine , و حضرتك صديقي المبرمج جربتها بتاع 253234 مرة لما استعملت ال Switch-Case او ما شابها 🙂

في النظم دي انا عندي : 
– اول حاجة finite set of states و خلينا نسميها Q

– عندنا finite set of input symbols زي برامج الغسالة او اختيارات الATM و خلينا نسميها I

– و عندك finite set of output symbols و هنسميها Z

– لو عايز اتنقل من حالة لحالة, لازم يخش انبوت I يحولني لstate معينة Q و دي هنعبر عنها رياضية بدالة بتعمل mapping عن طريق الI و الQ زي كده I x Q → Q و دي اسمها سيجما او ∂

– لو عايز بعد انبوت معين اطلع output معين, زي ان العملية خلصة واستلم فلوسك, لازم هعمل دالة رياضة بتعمل ,mapping للانبوت و الستيت لاوتبوت معين, يعني
I x Q → Z و دي اسمها W

لو جمعنا دول مع بعض في tuple هتبقي كده : (Q, I, Z, ∂, W) و دي اسمها M (رمز للاوتوماتا مش اكتر)

يعني انا قدرت اوصف اي سيستم في الدنيا ليه عدد حالات محدود بشكل رياضي كده

M = (Q, I, Z, ∂, W)

———————-

تعالي نطبق ده بقي عالATM ؟

 
Q = States = {first screen – card inserted – cash out – cash amount screen – pin screen }

I = Inputs = button clicks = {0..9 , enter , cancel } and so on

Z = outputs = {cash – error messages} and so on

∂ = transition function = rules to move forward in the process

W = output function = the rules to output the money in case of success

بأستخدام دول بقي, تقدر تحولهم ﻷي شكل رياضي او ميكانيكي او برنامج او ان شاالله التيلر اللي في البنك , نفس العملية بقي ليها شكل رياضي ف-تقدر تحققها في اي وقت و ب-أي شكل 🙂

———————-

بنفس الطريقة دي , بس باختلاف الstates و عددهم و شوية ظروف تانية, بيتعمل modeling رياضي ﻷي حاجة من اول تكاثر البكتيريا و تفاعلها سوا, لحد برامج الكمبيوتر اللي بتشغل المصانع و نظم التحكم الرقمي اللي بتشغل ال 3d printers و الCNC

شوفت انت ازاي كل حاجة مربطة ببعض, بتوع علم الاعصاب طلعوا مودل للدماغ استخدموا بتوع الرياضة عشان يعملوا موديل للعمليات المنطقية استعمله بتوع الالكترونيات عشان يعملولك الكمبيوتر اللي بتوع السوفتوير استعملوا فيه الاوتوماتا عشان تسحب مرتبك من الATM

———————-

الملحوظة المهمة بقي, هي ان السيستمز كتير منها في ارض الحياة, زي الكمبيوترات, ليها infinite states تقدر تتحرك بيها , و ده بدايته تحدي كده عمله الرياضي المشهور ديفيد هيلبرت و التاني ويليام اكرمان, بيتكلموا فيه عن حاجة في المنطق الرياضة اسمها مشكلة القرار, اللي هي الEntscheidungsproblem , واللي قدر يحلها بشكل منفصل في نفس التوقيت كل من الان تيورينج و الوزنو تشرش زي ما قولنا البوست اللي فات, و فيما بعد طلعوا ورقة بحثية موحدة اسمها ال Church–Turing thesis
بتوضح ازاي اصلا الكمبيوترات بتشتغل كAutotmata , و اللي منها طلع الImperative programming و ال Functional Programming

ده بقي موضوع البوست الجاي 🙂

#هاسكل_بالعربي

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog at WordPress.com.

Up ↑

Create your website at WordPress.com
Get started
%d bloggers like this: