Learnability Boundary: How Complex Can Neural Networks Learn Pseudo-Random Sequences?

Classical information theory assumes observers have unlimited computational power, making pseudo-random numbers "low entropy." However, for computationally bounded neural networks, the same data may be completely unlearnable noise. This paper experimentally explores the boundary of neural network learnability: from simple periodic patterns to cryptographically secure random numbers, we identify where Epiplexity (extractable structure) transitions from non-zero to zero. We train identical Transformer architectures on 6 sequences of varying complexity and find: (1) Pseudo-random sequences with state space ≤256 (simple LCG, 5-bit LFSR) can be perfectly learned (100% test accuracy); (2) Pseudo-random with state space 2³¹ (glibc LCG) is completely unlearnable (test accuracy = random guessing); (3) 31-bit LFSR exhibits partial Grokking—the model learns 1 bit of the sequence's pattern (50% accuracy) but cannot learn the remaining 7 bits. These findings validate the core prediction of the Epiplexity paper (Finzi et al., 2026): information is observer-dependent; the same data presents different learnability to observers with different computational power. Key contributions: - Experimental identification of the learnability phase transition boundary (between state space 256 and 2³¹) - Discovery of "partial Grokking" phenomenon in LFSR-31 (learning only 1 bit of 8) - Connection between Epiplexity theory and Grokking manifold discovery Code and data: https://github.com/lmxxf/grokking-train-learnability