0
$\begingroup$

As we know, formal language can be regarded as a set of strings of alphabet, and real number can be regarded as sequence generated by set of integers, for example, denominators of the simple continued fraction may form a set.

Algorithms analyze language and algorithms decide or output set of integers generating reals. Now, are there any transformation or correspondence between language and real number, which keep the computational complexity in same class? As we know, Godel encoding may be such a kind of transformation. Any reference?

Also, we hope the transformation is bijective.

Improve this question
$\endgroup$
5
  • $\begingroup$ You didn't mention computable/definable numbers (en.wikipedia.org/wiki/Computable_number). Does it relate to your question? $\endgroup$
    – Luc Guyot
    Commented Dec 23, 2017 at 10:15
  • $\begingroup$ @LucGuyot it is related. but since a set of integers can be regarded as equivalent to a real, I think it is not necessary to mention it. $\endgroup$
    – XL _At_Here_There
    Commented Dec 23, 2017 at 11:11
  • 1
    $\begingroup$ The question seems to be: can we construct a bijection between the set of expressions in a formal language and the set of real numbers? If this is what you are asking, the answer is trivially no, because the two sets have different cardinalities (unless you allow uncountable languages, like adding a constant symbol for every real number). $\endgroup$
    – Wojowu
    Commented Dec 23, 2017 at 11:18
  • $\begingroup$ Maybe you want to use the rationals since infinite sequences of symbols aren't usually considered. Also, the "alphabet" used for reals is infinite. $\endgroup$
    – Aaron Meyerowitz
    Commented Dec 23, 2017 at 14:57
  • $\begingroup$ @Wojowu no, You have misunderstood what I mean. a real may be regarded as a set of integer, so I just ask whether there is an encoding or map or bijection which transforms a real into a language or a language into a real. In such a way, we may construct two algorithms for a language and a real which keep the computational complexity in same class. $\endgroup$
    – XL _At_Here_There
    Commented Dec 24, 2017 at 3:06

0

Reset to default

You must log in to answer this question.