Decidable language that has no finite description? A language is a collection of strings--assuming we have an infinite number of words then concatenating this collection (keeping things simple,  normally you need to at least be able to tell where one word ends and another begins) and viewing the language as the resulting single big string, if the Kolmogorov complexity of this string is infinite can the language still be decidable?
This is asking if a language without a finite description can be decidable...also maybe sort of like asking if a language that is not constructible can still be decidable?
If I were to guess, I would say why not..? For example, a language could be given to you as an infinite table of rules (programs) for membership (that, per our condition above, can't be compressed into a smaller set of rules) paired with all words, but have only a finite number of the them be conditions for any particular word or group of words to be members. It is not your job to build such a table but once given such a table you could, when given a word, seek the rule in the table corresponding to that word (if the table is neatly organized this should be possible as to decide any particular word you ever only need to access a finite position on the table), check that word against that rule (run the program that is there on its word), and if doing so is computable for every rule in the table then the language specified by the infinite table should be decidable but at the same time not necessarily be finitely expressible.
Thanks!
Unless you want to be more rigid in what you allow as a &quot;description&quot;, every decidable language has a finite description - precisely the Turing machine that decides it. This Turing machine must exist (otherwise the language would not be decidable).
Although we often thing of automata as machines that do work, mathematically they're just a way of, in a certain sense, compressing the table that says &quot;yes&quot; or &quot;no&quot; for every string (over the given alphabet).