Skip to main content
9 events
when toggle format what by license comment
Jul 8, 2019 at 11:37 vote accept CommunityBot
Jul 8, 2019 at 11:07 comment added John L. Let us continue this discussion in chat.
Jul 8, 2019 at 11:04 comment added user99674 I just want to make sure - is my solution to the exercise actually valid? Can a turing machine make a "pesudo" move without reading anything from the input? If I can't do that, those moves would ruin the $\log_2n$ symbols remembered by the machine you defined.
Jul 8, 2019 at 11:02 comment added John L. It might have been less confusing had I written "$M_L$ halts in all cases. The language $M_L$ acceptes is $L$." instead of "$M_L$ decides $L$".
Jul 8, 2019 at 10:19 comment added John L. Yes, you have done the exercise correctly. It could have been slightly better if "$2^{|x|}$ moves" could have been "$2^{|x|}-|x|$ moves".
Jul 8, 2019 at 10:15 comment added John L. This machine works for any unregcognized languages, including undecidable languages. Note that words are usually assumed to be finite length. I was just being extra clearer in writing " of words of finite length".
Jul 8, 2019 at 8:29 comment added user99674 Exercise: I can tell that $\delta$ would also be infinite now so such a TM would also not contradict Church-Turning thesis with its calculating power becuase we don't know how to build such a machine in a reasonable time. implementation: $M$ starts at $q_0$. on input $x$ of finite length that is put to the right of its head, $M$ will read the entire input and stay in $q_0$, after that it'll make a pesuedo $2^{|x|}$ moves. Then change state to $q_1$, an accpeting state if the last $[\log_2n] = |x|$ cells that were read are in $L$, otherwise $q_2$, a rejecting state. Is that a good direction?
Jul 8, 2019 at 8:26 comment added user99674 When L is infinite we get infinte $Q, \delta$ and therefore can't build such a machine. Why does this machine work for unrecognized languages and doesn't work for undecideable languages though?
Jul 8, 2019 at 6:20 history answered John L. CC BY-SA 4.0