Editing Chomsky hierarchy (section)

===Recursively enumerable (Type-0) grammars===
{{main|Unrestricted grammar}}

Type-0 grammars include all formal grammars. There are no constraints on the productions rules. They generate exactly all languages that can be recognized by a [[Turing machine]], thus any language that is possible to be generated can be generated by a Type-0 grammar.<ref name=Sipser-1st /> These languages are also known as the [[recursively enumerable language|''recursively enumerable'']] or ''Turing-recognizable'' languages.<ref name=Sipser-1st>{{cite book |last=Sipser |first=Michael |author-link=Michael Sipser |year=1997 |title=Introduction to the Theory of Computation |edition=1st |publisher=Cengage Learning |isbn=0-534-94728-X |page=[https://archive.org/details/introductiontoth00sips/page/130 130] |url=https://archive.org/details/introductiontoth00sips/page/130 |url-access=registration |quote=The Church-Turing Thesis }}</ref> Note that this is different from the [[recursive language]]s, which can be ''decided'' by an [[machine that always halts|always-halting Turing machine]].