Quantcast
[ 3 / biz / cgl / ck / diy / fa / g / ic / jp / lit / sci / tg / vr / vt ] [ index / top / reports / report a bug ] [ 4plebs / archived.moe / rbt ]

Due to resource constraints, /g/ and /tg/ will no longer be archived or available. Other archivers continue to archive these boards.Become a Patron!

/sci/ - Science & Math

Search:


View post   

[ Toggle deleted replies ]
>> No.7898946 [View]
File: 172 KB, 1280x850, Languages Chomsky hierarchy.jpg [View same] [iqdb] [saucenao] [google] [report]
7898946

>>7898930
Me again. Just wanted to point out that the reason you use all of that "smashing your fingers into a keyboard" stuff, as you nonsensically put it, is because those theorems prove useful in distinguishing subsets of languages and telling you where a language lives.

The reason for doing this is because where a language lives tells you whether or not it's membership problem is
>decideable (i.e. if there exists a computable function that when given a word will determine in finite time if the word is or is not in the language)
>recognizable (i.e. if there exists a partially computable function that when given a word will determine in finite time if the word is in the language but may fail to terminate if the word is not in the language)
and it will tell you what type of function can be used to do it, how to produce such a function, the time complexity of the function, and so on.

This may not sound very useful to you since you probably don't care about languages but take note that languages really just encode information. One could talk about the language consisting of all binary strings that encode jpeg images of your mom in a gang bang. Then one could ask whether there exists a function that when given a binary string encoding for a jpeg, will decide if the picture contains your mom in a gang bang. Whether or not this is true depends on the structure of the language describing such binary strings.



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