Timeline for Easy-to-prove example of non-contextual language
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 29, 2021 at 10:06 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Aug 30, 2021 at 9:17 | answer | added | Thomas Baruchel | timeline score: 1 | |
| Aug 25, 2021 at 14:02 | comment | added | rici | I had a feeling that would be the case which is why I preflighted that as a comment. It at least clarifies what you are looking for. | |
| Aug 25, 2021 at 8:17 | comment | added | Thomas Baruchel | @rici While your answer is perfect, I had something rather different in mind: first, proving the language isn't context-sensitive by relying on some common specific properties of such languages (like my other examples for each respective type); second, showing some "minimal" language from the next type; third, some kind of "concrete" language which could be illustrated by actual examples of words. | |
| Aug 24, 2021 at 20:53 | comment | added | rici | Do you consider a universal turing machine implementation to be simple enough to qualify for your intuition? Because it is clear that this language is undecidable and hence type 0: $\{<M>\omega\mid <M> \text{ describes TM }M\text{ and }M\text{ halts on input }\omega\}$ | |
| Aug 24, 2021 at 9:05 | review | First posts | |||
| Sep 7, 2021 at 9:02 | |||||
| Aug 24, 2021 at 9:01 | history | asked | Thomas Baruchel | CC BY-SA 4.0 |