Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Turing Machine and (BF) Programming Language

Turing Machine and (BF) Programming Language

Presented as a 'Programming Language' course material, Amirkabir University of Technology, Tehran, Iran.

Morteza Ansarinia

January 10, 2006
Tweet

More Decks by Morteza Ansarinia

Other Decks in Programming

Transcript

  1. اه نابز توافت • pushdown without LIFO • Infinite symbol

    array (tape) • Infinite? Control Unit Tape Read-Write head
  2. گنیروت نیشام یمسر فیرعت M = (Q , ∑ ,

    Γ , δ , q0 , □ , f) δ = Q × Γ Æ Q × Γ × { L,R }
  3. اب گنیروت نیشام k ات tape • رد توافت نیا

    اب ،یلومعم گنیروت نیشام دننام δ : δ = Q × Γk Æ Q × Γ × { L,R,S }k • یلومعم گنیروت نیشام زا نیشام نیا هک نیا مهم ی هتکن تسین رت دنم تردق
  4. راک زرط زا یا هنومن δ … a b c

    … δ(q 0 ,a) = (q 1 ,d,R) Internal State q 1 Internal State q 0 … d b c …
  5. گنیروت نیشام زا یا هنومن … a a … q

    0 … a b … q 0 … a b … q 0 … a b … q 1 δ(q 0 ,a) = (q 0 ,b,R) δ(q 0 ,b) = (q 0 ,b,R) δ(q 0 ,□) = (q 1 , □,L) Q = {q 0 , q 1 } ∑ = {a, b} Γ = {a, b , □} F = {q 1 }
  6. گنیروت نیشام زا رگید یا هنومن S1 1R 0 S5

    S5 1L 1 S5 S5 0L 0 S4 S4 1L 1 S4 S3 1R 1 S3 S4 1L 0 S3 S3 0R 0 S2 S2 1R 1 S2 S2 0R 1 S1 New State Write Read Old State
  7. 11011 S1 14 10011 S5 13 10011 S4 12 10011

    S4 11 10010 S3 10 1001 S3 9 1001 S2 8 1101 S1 7 0101 S5 6 0101 S5 5 0101 S4 4 0100 S3 3 010 S2 2 01 S2 1 11 S1 0 Tape State Step
  8. Halt state • نیشام ی هسورپ نتفای نایاپ • δ

    تسا هدشن فیرعت • فیرعت مدع δ یارب final states – هب final states هب رجنم ندیسر halt دوش یم
  9. تیاهن یب رود • نودب گنیروت نیشام halt • یور

    تکرح tape هشیمه یارب ،نآ رییغت نودب
  10. Deterministic و Non-deterministic • کی رگا entry بیکرت کی یارب

    state و symbol دشاب هتشاد دوجو • کی زا شیب رگا entry بیکرت کی یارب state و symbol دشاب هتشاد دوجو • تسا نکمم مه هب عون ود نیا لیدبت
  11. گنیروت نیشام Universal • Transition function هک دشاب یتروص هب

    دناوت یم یور زا tape دزاسب ار دوخ • دشاب هتشادن یتباث ی همانرب هک تشاد ینیشام ناوت یم “It can be shown that a single special machine of that type can be made to do the work of all. It could in fact be made to work as a model of any other machine. The special machine may be called the universal machine“ Alan Turing
  12. گنیروت نیشام یاهدربراک • Accepter – کی شریذپ هتشر کی

    رد نابز صخشم • Transducer – عبات دنک یم دیلوت یصاخ یجورخ ،یدورو کی یور هک ی
  13. accepter • هتشر کی اب عورش • نیتسخن ناکم head

    هتشر پچ تمس رد ) عورش نامه هتشر ( • کی هب هک یماگنه ات همادا final state و دوش دراو متسیس halt دوش } , , some for : { * 2 1 2 1 0 Γ ∈ ∈ ⎯→ ⎯ ∑ ∈ = + x x F q x q x q ω L(M) f f
  14. transducer • ریذپ هبساحم یاه عبات D F q f

    q q f f M ∈ ∈ ⎯→ ⎯ ω ω ω all for ), ( 0
  15. گنیروت هیرظن • لباق یکیناکم یاه شور هلیسو هب هک

    یا هبساحم ره لباق زین گنیروت نیشام ی هلیسو هب ،دشاب هبساحم تسا هبساحم • ی هلیسو هب رگا طقف و رگا ،تسا یکیناکم هبساحم کی دشاب هبساحم لباق گنیروت نیشام
  16. ؟درکن هابتشا زورما ات گنیروت ارچ • یاهرتویپماک ی هلیسو

    هب دناوت یم هک یا هبساحم ره دوش یم ماجنا مه گنیروت نیشام اب ،دوش ماجنا لاتیجید • ی هلیسو هب هک دنک داهنشیپ یا هلسم هتسناوتن یسک زونه لح هب رداق گنیروت نیشام یلو دشاب لح لباق یمتیروگلا دشابن نآ • یلو هدش داهنشیپ اه هبساحم نیا یارب یرگید یاه شور تسین دنم تردق گنیروت نیشام ی هزادنا هب مادک چیه
  17. دلوت • لاس رد رلوم یاقآ 1993 • کچوک یلیخ

    یرلیاپماک زا هدافتسا اب هداس ینابز • نابز زا ماهلا FALSE یرلیاپماک اب 1024 یتیاب • یاهرلیاپماک bf زا رت کچوک مجح اب 200 تیاب
  18. نابز راتخاس bf • هیارآ ی 30,000 ییات ) رفص

    همه ییادتبا تلاح ( • Pointer اه هیراد یور تکرح لباق یا ) ییادتبا تلاح پچ تمس رد ( • یجورخ و یدورو یارب هیارآ ود ) تمرف اب ASCII ( – دیلک هحفص دننام یدورو – شیامن هحفص دننام یجورخ • چیه symbol درادن دوجو یرگید
  19. نابز هب لیدبت c char* ptr; > ++ptr; < --ptr;

    + ++*ptr; - --*ptr; . putchar(*ptr); , *ptr=getchar(); [ while(*ptr){ ] }
  20. هتکن دنچ [-] یلعف هیارد ندرک رفص ,[.,] یدورو پاچ

    ) ای رفص هیارد ماگنه ات EOF ( >,[.>,] یدورو پاچو هریخد
  21. bf رگید یاه • عون ،هیارآ هزادنا ،هیارد عون ای

    هزادنا رد توافت commenting همانرب نایاپ یراذگ هناشن و • doublefuck ود و هیارآ ود اب pointer – یلبق یاهروتسد رب هوالع مود هیارآ یارب دیدج یاهروتسد : • ^ • V • \ • / • : • ; • { • }
  22. bf رگید یاه • P’’ اب زرا مه bf و

    یدورو یاراد هک توافت نیا اب ،تسا تسین یجورخ • pBrain یاراد procedure تسه مه . • Cow نامه bf یاه نامرف هک توافت نیا اب ،تسا bf فلتخم یاه تلاح Moo دنتسه . • Ook تاروتسد زین bf فلتخم یاه تلاح اب ار Ook! و Ook. و Ook? دهد یم رارق زرا مه .
  23. اه عجرم An Introduction To Formal Language and Automata Peter

    Linz Google & Wikipedia : Turing Machine brainfuck