0
$\begingroup$

Let us define a one-to-one function $f$ that maps binary strings of length $n$ to ternary strings of length $n$ such that if $x$ is random then $f(x)$ must be random. My question

Is there an algorithm that computes such function?

  • 0
    What about $f(x) = x$? I guess I must be missing something...2011-02-28
  • 0
    I guess identity function is excluded. $x \in \{0,1\}^*$ while $f(x) \in \{0,1,2\}^*$2011-02-28
  • 0
    @turk: Don't you mean $x \in \{0,1\}^n$?2011-02-28
  • 1
    "one-to-one" means injective, right? because there are no surjections from binary strings of length $n$ to ternary strings of length $n$.2011-02-28
  • 1
    What is a random string?2011-02-28
  • 0
    @Moron: if f(x)=x, there will be no 2's in f(x), so it won't look random.2011-02-28
  • 0
    @Ross: Well, if $x$ can be considered random... Of course, as Qiaochu asked, what does random really mean here?2011-02-28
  • 0
    @Moron: I was thinking in terms of compressible-is there a (much) shorter description. And if you know there are no 2's, you can save a factor of $\log_2(3)$2011-02-28
  • 2
    @Ross: I was thinking about 'unpredictable'. But that is not too rigorous. Of course, OP should ideally tell us...2011-02-28
  • 0
    @Moron: agreed on OP should answer. "Random" is not well-defined.2011-02-28
  • 0
    @Ross, I guess you can assume that random means incompressible strings (using Kolmogorov Complexity).2011-02-28
  • 0
    @turkistany: that is the sense of my answer. If somebody knows the algorithm, they will know the range of $f(x)$ otherwise they will have to look at the output and it may look random.2011-02-28
  • 0
    @Ross, Do you have a concrete algorithm that would compute $f$?2011-02-28
  • 0
    No, but there are many. You could feed your $x$ as a seed (maybe broken into pieces) to your favorite random number generator or encryption algorithm.2011-02-28

2 Answers 2