Turing Machine Example and Computation (Can you guess what it does?)

แชร์
ฝัง
  • เผยแพร่เมื่อ 17 ธ.ค. 2024

ความคิดเห็น • 63

  • @RandomPerson-zr5ix
    @RandomPerson-zr5ix 3 ปีที่แล้ว +25

    Thank you, you made learning TOC much easier, hope your channel will receive more attention

    • @EasyTheory
      @EasyTheory  3 ปีที่แล้ว +2

      Thanks very much!

  • @jewelleharper6285
    @jewelleharper6285 3 ปีที่แล้ว +19

    So I am doing coursework from home this term b/c my immune system has issues and covid is still a thing... I want to let you know, I don't even really watch the lecture recordings. I come here and Voila! I understand!!!!! It's almost magical.

    • @brendawilliams8062
      @brendawilliams8062 3 หลายเดือนก่อน

      I’m saving as many lectures as I am offered. An amazing Educator. Obviously loves to teach. Thankyou

  • @FURKANHAMZABOLAT
    @FURKANHAMZABOLAT 6 หลายเดือนก่อน +1

    I watched videos related to the topic both in my own language (Turkish) and in English. I couldn't understand the topic even from Indian professors. But when I watched your video, I really understood the topic. You're amazing.

  • @Irem-zv6jc
    @Irem-zv6jc 3 ปีที่แล้ว +9

    you saved my lifeee !! you are better than my professor lol

    • @EasyTheory
      @EasyTheory  3 ปีที่แล้ว +1

      You're very welcome!

  • @iamasteriix
    @iamasteriix 2 ปีที่แล้ว +17

    "Look at q_0, and we see a 0 on the tape. Well! By Golly!"
    - Prof. Dougherty, 2022

    • @EasyTheory
      @EasyTheory  2 ปีที่แล้ว +6

      I need to add "By Golly" to my phrase arsenal.

  • @PCguyNoah
    @PCguyNoah หลายเดือนก่อน

    Thank you! You explaination made so much more sense than my professors.

  • @Ayesha-uw4dt
    @Ayesha-uw4dt 10 หลายเดือนก่อน +2

    you're an absolute SLAY! great explanation

  • @akashnayak3752
    @akashnayak3752 ปีที่แล้ว +2

    The TM is accepting language, L = {0^2^n | n>=0}
    But we have to add one extra transition to the diagram in the video, i.e. at state q3 add a self-loop (X->R)

    • @shifa_imran
      @shifa_imran ปีที่แล้ว

      how do u get to know this?

    • @akashnayak3752
      @akashnayak3752 ปีที่แล้ว

      @@shifa_imran The same TM diagram is given in the TOC book of Michael Sipser. Do refer to it and you will understand better.

    • @begumaygun9173
      @begumaygun9173 10 หลายเดือนก่อน

      @@akashnayak3752 Do you have any ideas where I can find information about "a^c^b" ?

    • @akashnayak3752
      @akashnayak3752 10 หลายเดือนก่อน

      @@begumaygun9173 Sorry I really have no idea.

    • @begumaygun9173
      @begumaygun9173 10 หลายเดือนก่อน

      @@akashnayak3752 thank you anyway

  • @hudson5610
    @hudson5610 3 ปีที่แล้ว +4

    I appreciate how clear the video is and how the TM works - but it would be great if you told us what it did. It seems to be replacing the 0's with X's but I am not sure if it is only checking the tape for X's and 0's or also checking for an even number of 0's.

    • @Shadowdoctor117
      @Shadowdoctor117 3 ปีที่แล้ว

      This is super late, but I believe it checks for an even input of 0. I tried 5 0's and it reject, but 6 0's accepted and 2 0's accepted

    • @GDX17
      @GDX17 2 ปีที่แล้ว +1

      @@Shadowdoctor117 it accepts a single 0

    • @robharwood3538
      @robharwood3538 2 ปีที่แล้ว

      @@Shadowdoctor117 And it doesn't actually accept 6 0s. Try it while actually tracking the changes to the tape to see.

    • @rathors7184
      @rathors7184 2 ปีที่แล้ว +6

      It's seeing if there are 2^n zeros. It cuts the number of zeros in half on every sweep, essentially keeping track whether if there are an even number of zeros on every sweep. If by the time there is only one zero, it accepts it. If at any point there was an odd number of zeros, it rejects it.

    • @armangundogan6142
      @armangundogan6142 ปีที่แล้ว +2

      @@rathors7184 but it doesn't accept 8 0's, it becomes UX0X0X0X,U and when back to beginning it gets stuck in q3 because there is no 0 after a 0, so it doesn't accept 2^3, actually it doesn't even accept any more 0's than 4 0's, and it has to start with a 0, and after 2 0's, other two 0's must be consecutive and it doesn't accept 3 total 0's, other than these conditions it accepts x infinitely, edit: i saw the channel's comment and x is meant as tape language only so not input, then that makes this machine accept 2^n, 0

  • @krishnakarthik4752
    @krishnakarthik4752 ปีที่แล้ว

    Love your intro to computation lectures; we have a similar course in uni and I find the lectures on turing machines a bit confusing.

  • @BraisleiroNaArabia
    @BraisleiroNaArabia 4 ปีที่แล้ว +2

    The video is awesome, thank you. What would be great to have is how do we start from a definition of a language to implementing a TM for it

    • @EasyTheory
      @EasyTheory  4 ปีที่แล้ว +3

      It's often hard to do so for an arbitrary language, but what I would do is to split the language into "simpler" languages, and then combine them. For TMs specifically, think first about how the "layout" of the tape contents should be, and then design the TM around that idea (or if you want to use multiple tapes, etc.).

  • @sbinsdca
    @sbinsdca 2 หลายเดือนก่อน

    I'm surprised I never ran into TM's in discrete math. I was reading an article on AI and it mentioned the TM. So, here I am :)

  • @milanrai3607
    @milanrai3607 หลายเดือนก่อน

    This is okay to check the acceptance or rejection of a given string once we have the transition graph. However, I am not sure about drawing a transition graph for a given language. Your lectures seem to be for the lecturers, but learners.

  • @roqueutah
    @roqueutah 3 ปีที่แล้ว +2

    Hello Professor Dougherty, It would be beneficial to post PDF, JPG, or PNG of the machine to follow the video. I use windows snipping to copy the image on the screen. Thanks

  • @ChauDang-bm1nf
    @ChauDang-bm1nf ปีที่แล้ว +1

    Hi Professor,
    Could you please explain how to design a Transducer TM that can stimulate a DFA ?
    Thank you very much

  • @khanmethun6935
    @khanmethun6935 หลายเดือนก่อน

    how do you decide on the transition function after seeing the problem what is the fundamental of it?

  • @Lordycal
    @Lordycal ปีที่แล้ว

    you made my mind click thank you

  • @Lordycal
    @Lordycal ปีที่แล้ว

    how would a transition function look with this? is there a video on that?

  • @1UniverseGames
    @1UniverseGames 2 ปีที่แล้ว +1

    I have one question sir, how can we design a TM such that (0^n 10^3n) how do we solve this?

  • @Evarunkumar
    @Evarunkumar 9 หลายเดือนก่อน

    thanks a lot for you effort

  • @ABIRAMISKA
    @ABIRAMISKA ปีที่แล้ว

    thanks dude

  • @ahmetkarakartal9563
    @ahmetkarakartal9563 11 หลายเดือนก่อน

    wow, thank you so much

  • @GDX17
    @GDX17 2 ปีที่แล้ว

    is x part of the input alphabet or only the tape alphabet?

    • @EasyTheory
      @EasyTheory  2 ปีที่แล้ว +2

      Great question. It can be either, but I intended the alphabet to just be {0}, and not have x. If it did, then the language would be substantially different.

    • @GDX17
      @GDX17 2 ปีที่แล้ว +1

      @@EasyTheory So given that the input alphabet is {0} it seems that the accepted language would be limited to {0, 00, 0000}. Any other combination of 0's seems to end up failing in state q3 with either an x or a blank input, except for an empty string which will fail in q0.

    • @moatef1886
      @moatef1886 2 ปีที่แล้ว

      @@GDX17 Are you sure about this? Think again about possible strings that could be in this language.

    • @alexm.2960
      @alexm.2960 2 ปีที่แล้ว

      @@moatef1886 does it accept whenever the amount of zeros is equal to a power of two?

    • @moatef1886
      @moatef1886 2 ปีที่แล้ว +1

      @@alexm.2960 Yes. :)

  • @DanChristos
    @DanChristos ปีที่แล้ว

    So does it accept even numbers?

    • @dn6824
      @dn6824 6 หลายเดือนก่อน

      it recognizes {0^(2^n) | n ≥ 0}. in other words, strings of 0's whose lengths are powers of 2

  • @careenwasonga
    @careenwasonga 7 หลายเดือนก่อน

    God bless you!

  • @TavartDukod
    @TavartDukod 3 ปีที่แล้ว +2

    Okay, I think it accepts strings that satisfy this regular expression: 01*(01*(00)?)?1*.

    • @robharwood3538
      @robharwood3538 2 ปีที่แล้ว

      This is correct if the input alphabet consists only of 0s and 1s. It can also be equivalently written as 01*(01*(00)?1*)? with the final 1* inside the group, thus being included in the ? ('optional') quantifier at the end.
      However, if we allow for *any* symbols as input on the tape, especially including _ ('space') as a possible input, then the regular expression is a little bit different (here I will use the common dot-symbol "." to represent 'any symbol' as is common in regular expressions):
      01*(01*(00)?1*)?(_.*)?
      In other words, if your input tape has a space followed by any string of any symbols at the end, then it will also be accepted. You could think of this as working very similar to how end-of-line comments work in many programming languages. Here, instead of the typical // delimiter for comments, it just uses a single _ (space-symbol).
      [This explains why I suggested the equivalent with the final 1* inside the first optional group, since the structure of the regular expression better matches the structure of the Turing machine graph.]
      The full language accepts both:
      0110100111
      but also the same string followed by a space-delimited 'comment':
      0110100111_Hello, world!
      Or, if the input alphabet is restricted to only 0, 1, and _, then you could write the comment in some binary (or ternary!) code like this one with a meaningless/random comment at the end:
      0110100111_10101110101000__001_1

    • @dn6824
      @dn6824 6 หลายเดือนก่อน

      it recognizes {0^(2^n) | n ≥ 0}. in other words, strings of 0's whose lengths are powers of 2

    • @dzbro1194
      @dzbro1194 7 วันที่ผ่านมา

      @@dn6824 0^8 is not accepted isnt it?

    • @dn6824
      @dn6824 7 วันที่ผ่านมา

      @@dzbro1194 yes it does. try running thru the state machine for n=3, or in other words 00000000 like you mentioned

    • @dzbro1194
      @dzbro1194 7 วันที่ผ่านมา

      @@dn6824
      idk i tried doing it multiple times and i keep getting stuck with X as input on q3 with no possible transitions.
      $00000000u
      $u0000000u
      $uX000000u
      $uX000000u
      $uX0X0000u
      $uX0X0000u
      $uX0X0X00u
      $uX0X0X0Xu
      $uX0X0X0Xu
      ...
      $uX0X0X0Xu ; u -> R
      $uX0X0X0Xu ; X -> R
      $uXXX0X0Xu ; 0 -> X, R
      $uXXX0X0Xu ; X -> R
      $uXXX0X0Xu ; 0 -> R
      then we have X on q3 and no possible transitions.
      pls tell me if you see what im doing wrong.

  • @diddleyy2759
    @diddleyy2759 2 ปีที่แล้ว

    So I think the language describes all strings composed as 0{00,x}*

  • @juanbomfim22
    @juanbomfim22 3 ปีที่แล้ว +2

    I guess the machine computes strings with just one zero or even no. of zeroes

    • @robharwood3538
      @robharwood3538 2 ปีที่แล้ว +1

      Nope. Doesn't accept 6 or more 0s either.

    • @dn6824
      @dn6824 6 หลายเดือนก่อน

      it recognizes {0^(2^n) | n ≥ 0}. in other words, strings of 0's whose lengths are powers of 2

  • @soulmusic6530
    @soulmusic6530 4 ปีที่แล้ว +3

    Just wanted to say great videos, but could you please change the starting music..

  • @gabrielrubio922
    @gabrielrubio922 หลายเดือนก่อน

    this made no sense at all

  • @batteryjuicy4231
    @batteryjuicy4231 2 ปีที่แล้ว

    what degree teaches that stuff? because that's the path I want to follow(the math, theoretical aspect of cs)

    • @jesuyacked
      @jesuyacked 2 ปีที่แล้ว +1

      I'm on Computer Science and I study this stuff, maybe go to that or mathematics