0
$\begingroup$

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!

$\endgroup$

1 Answer 1

3
$\begingroup$

Unless you want to be more rigid in what you allow as a "description", 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 "yes" or "no" for every string (over the given alphabet).

$\endgroup$
3
  • $\begingroup$ oh ya you are totally right the solver itself is a compression of the language. But could the solver's code not also be infinitely long--as long as you only ever need to run a finite portion of it on any word then it could be ok? sorta same argument as my table example. $\endgroup$
    – DeeDee
    Commented Nov 18, 2020 at 0:52
  • 2
    $\begingroup$ No, it's part of the definition that a TM is finite - finite tape alphabet, finite number of states, which gives a finite number of transitions that are possible (even with nondeterminism), and that's basically the whole thing. $\endgroup$ Commented Nov 18, 2020 at 0:54
  • $\begingroup$ Sweet man thanks $\endgroup$
    – DeeDee
    Commented Nov 18, 2020 at 0:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.