What is the meaning of "w describes a halting TM" mean?

48 Views Asked by At

I was originally looking for languages that weren't context sensitive.

In Wikipedia (https://en.wikipedia.org/wiki/Chomsky_hierarchy), I believe the language $\{w | w \text{ describes a terminating TM} \}$ isn't a CSG. I'm not sure how a TM is "described" by a word. As far as I know a TM is a 7 tuple??

Also, could you give another example of a language which isn't a CSG.

1

There are 1 best solutions below

0
On BEST ANSWER

For any finite, discrete object $O$, it is always possible to find some way to encode $O$ as a string. The Turing machine (the 7-tuple you mention) is a finite, discrete object; therefore, you can design a string representation of it. The remark on Wikipedia is that the language encompassing all string representations for machines that halt is not a CSG, whatever your encoding scheme is.

More details on that encoding are found in these course notes and this CS Stack Exchange question.

As far as examples, Wikipedia is a good source. The true formulas in Presburger arithmetic and (though it's a bit silly, given your example) the set of Java programs that terminate are not expressible in a CSG.