[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

Search:


View post   

>> No.7898930 [View]
File: 27 KB, 642x417, language CFG hierarchies.png [View same] [iqdb] [saucenao] [google]
7898930

>>7898482
Recursive function theory is only studied in CS. It is often studied at either the undergraduate or graduate level (my university does it in undergrad). Furthermore, recursive function theory is only one model of computation and typically a course covering recursive function theory also covers many other non-trivial models of computation with the intention of proving equivalence. This is why in modern times we refer to the topic as computability instead of recursive function theory.

>>7898488
Computability is very closely related to formal language theory.

The big theorems in computability theory are
>S_{mn} theorem.
https://en.wikipedia.org/wiki/Smn_theorem
>Kleene's recursion theorems.
https://en.wikipedia.org/wiki/Kleene%27s_recursion_theorem
>Rice's Theorem.
https://en.wikipedia.org/wiki/Rice%27s_theorem
>A whole bunch of stuff about the Arithmetic Hierarchy
https://en.wikipedia.org/wiki/Arithmetical_hierarchy
>A whole bunch of stuff about encoding arithmetic, logic, languages, and a bunch of other shit.
>A whole bunch of stuff about recursively enumerable sets, oracles, and so on.
>A whole bunch of different models of computation and theorems proving equivalence between them.

Parsing theory is also very closely related to formal languages. Here the goal is to reason about languages and algorithms that can parse said language (and at what level of time complexity). In particular one typically deals with subsets of the set of context free languages (pic related). Depending on properties that the grammar has for the language one may be able to use different types of parsers, some simpler and more efficient than others. Furthermore, one may or may not be able to prove that two parsers parse the same language and one may be able to root out problems like ambiguity in the language specification.

There are also many other related topics including language theoretic security and graph grammars.

Navigation
View posts[+24][+48][+96]