1
$\begingroup$

Here is the problem: Let's say we have a random binary sequence, just an arbitrary sequence of zeroes and ones (of some arbitrary length of digits). Can we find an algorithm that would decode/decompress this sequence into a meaningful statement (say, in some natural human language)? I don't want to condition or bias on any particular human natural language, or really any other communication system (I suppose we could broaden to visual, audio, or other symbolic communication systems).

The idea is that we can take a natural language statement in text form, and then using lossless text compression, code it into a binary sequence that appears completely random. So one will see this sequence and think it is just meaningless and random, say, in the information theoretic sense. Then suppose one is presented with some other binary sequence that appears random. One might use this as an argument against the conclusion that this other binary sequence is stochastically random or lacks any meaningful information since we have an example of a sequence that appears random but in fact is actually compressed meaningful text. The idea comes from an intelligent design type argument against the idea of ever concluding something is stochastically random, i.e. that just because something appears random, one can never claim it is actually random (since some things that appear random are not). My perspective is that it is a bad argument (or even a purposefully misleading one).

Here is an attempt to put it symbolically. Suppose we have a binary sequence $\mathbf x$. Does there exist an text-to-binary algorithm $F$ and a meaningful text string $\mathbf s$ such that $\mathbf{x}=F(\mathbf{s})$.

For example, if I am presented with an arbitrary sequence such as:

$$0 0 1 0 0 1 0 0 0 0 1 1 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0 1 0 1 1$$

can I find an algorithm that this exact sequence is the result when the input string is

$$\text{''Apples grow on trees.'' } $$

or any other arbitrary but meaningful text statement?

Of course, maybe other algorithms decode the binary sequence to different text strings, but that is fine. My point is that even if we have a random binary sequence, generated by, say, coin flips or radioactive decays, then we can always find an algorithm that would encode meaningful text as that particular random sequence. I am hoping to avoid trivialities, e.g. a tailor-made algorithm that converts a pre-specified text string to the the specific sequence under question. I am hoping that the algorithm will be a general-purpose text compressing/encoding algorithm that can act on any text string from the given natural language.

I hope this question is understandable. I don't quite have a sophisticated enough understanding of information and computational theory to formulate it more clearly. Feel free to be as theoretical as desired in any comments, questions, or answers though.

$\endgroup$

3 Answers 3

3
$\begingroup$

The answer is Yes, such an algorithm exists. Suppose $x=00100100001111011110110110001011$ and $s=$"Apples grow on trees". There here is an algorithm $F$ that meets your requirement:

function $F(t)$:

  • If $t=$"Apples grow on trees", then return $00100100001111011110110110001011$.

  • Otherwise, do anything you want. (e.g., return the gzip compression of $t$)

If you additionally want $F$ to be bijective, that takes a little extra work, but that can also be arranged.

This is a rather trivial solution, so while this meets all your requirements, I suspect perhaps your requirements didn't accurately capture what you actually wanted to know.

$\endgroup$
3
  • $\begingroup$ I was hoping to avoid trivial solutions, and to only select from algorithms that have some reasonably large domain (say being able to operate on any text string of some fixed symbol set). But you seem to at least be confirming that given an arbitrary binary seq, we can find a general purpose text-to-binary algorithm that gives it as output with some meaningful text string as input. $\endgroup$
    – jdods
    Aug 19, 2021 at 3:24
  • $\begingroup$ @jdods, define "Trivial". My example function $F$ already has a large domain -- in fact, infinitely large -- it can operate on any text string. $\endgroup$
    – D.W.
    Aug 19, 2021 at 3:52
  • $\begingroup$ It is probably the case that my question is trivial! I don't know how to conceptualize the idea of a "legitimate text-to-binary-algorithm" but if that really is just identical to the space of functions (say with finite text string input as domain and binary sequence output), then yes, I can see how the question is easily solved in the affirmative. I may be erroneously thinking along the lines of fixing an algorithm and then varying the text input to see how large of set of binary sequences can I get. $\endgroup$
    – jdods
    Aug 19, 2021 at 11:51
2
$\begingroup$

We could actually speak of a compression algorithm.

Some compression schemes use prefix codes, which relies on how often a particular symbol appears, which is referred to as the frequency. The basic idea is that the symbols that appear most often are re-expressed as the smallest possible symbols. We call the output symbols code words.

For example, in your string "Apples grow on trees", the character "e" appears most often at 3 times, so we want to re-express this as small as possible. We will rewrite your entire string, and write the single bit "0" every time the character "e" appears in the string. Then, the four characters "p", "s", "r", and "o" each appear 2 times. So again, we will re-express them as new codes, and as small as possible. "0" has already been taken, so re-express them as "1000","1001","1010", and "1011". Then express the remaining characters as larger strings.

This is still pretty small for characters, and obeys the prefix code idea, which states that no code word, for example the bit "0", is a prefix of any other code word.

Using a system like this will ensure that basically any string will have a specific interpretation.

$\endgroup$
0
$\begingroup$

My 2 cents...

Can there be , Yes. But it kind depends on your depends definition of "meaningful-text-input"

Right now.. I would say not yet. A compression algorithm generates binary data, and each algorithm can generate different binary data.

but just given random pattern, not that I have found exactly. Well, until you explore writing the algorithm.

You have the trivial substitution, example from D.W. And a slight extension with a database to look up pattern replacements, a dictionary. This can get rather large quickly.

Off the top of my head... one method is using a Markov Chain. I can imagine using the binary input to walk a Windowed Markov Chain of words/letter/patterns to build the output text.

There are a few Markov chain programs out here that you could modify. a quick search you can find code to play with, even JavaScript.

This Markov Chain data can be built up by processing a set of text files into a database/dictionary

I assume you are receiving this pattern to be decoded, so long as both sides have the same built dictionary, any pattern can be decoded and output the same text for the same input. And many(not all) text can be encoded into a binary pattern, provided that all parts of the input text can be found in the Markov chain dictionary.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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