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.

Avatar for Morteza Ansarinia

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