Timeline for Turing machine where the next step is determined by the state and the symbols up to the read/write head
Current License: CC BY-SA 4.0
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 |