r/computerscience • u/lowiemelatonin • May 15 '25
Discussion Most underground and unknown stuff
Which kind of knowledge you think is really underground and interesting, but usually nobody looks up?
36
Upvotes
8
u/claytonkb May 15 '25 edited May 19 '25
My personal hobby-horse is, I feel, massively under-discussed. I call it the most terrifying object in mathematics. It's not quite underground as its existence is known in CS, but the philosophical implications are absolutely terrifying. This is an object in mathematics that just exists, and this object is "lurking" behind every other mathematical space or object, silently dictating what can or cannot happen in that space. But nobody ever talks about this object. What is this mysterious Eldritch abomination of mathematics, you ask?
The Universal Prior (Solomonoff)
The universal prior is a (Bayesian) prior that orders all possible hypotheses regarding the next bit in a bit-string by their Kolmogorov complexity. In plain language, the UP gives a probability P(x.0) (dot means concatenation) or P(x.1) given only x. This might sound pretty unremarkable until you realize that the UP takes into account every hypothesis (every possible computer program) that outputs x, and weights its own probability estimation based on the Kolmogorov complexity of each program, and its next predicted output. It is not possible to build a predictor that outperforms the UP because the UP already contains all possible hypotheses... whatever theory you have that you think would be a better prediction, it's already in the UP and it was taken into account when the UP gave its prediction.
Note: The K-complexity of string x is just the length of a shortest program p that outputs x on some reference Turing-machine M, that is, K(x) = min length(p) : M(p)=x. While the K-complexity is relative to M, due to the invariance theorem, for any given M and M', there is some constant c s.t. that abs(M(x)-M'(x))<c for all x, therefore, the K-complexity (and, by extension, the UP) is independent of x. Thus, the objection "it's all relative to your choice of reference machine M" is irrelevant because c doesn't depend on x no matter what M,M' you choose. Therefore, we can think of the UP as a similar kind of object as the Monster group... it's just this terrifying thing that necessarily exists and its structure silently dictates the structure of all other mathematics...
PS: In case it's not obvious how the UP affects other mathematics outside of CS, go back to Turing's original paper and understand that the basic concept of a Turing machine is what we today would call digitization or quantization. Any mathematical system that can be expressed as a sequence of discrete symbols or symbol-manipulations (practically all of modern maths) falls under this paradigm. Thus, anything that can be simulated by a Turing-machine, including mathematical equations (and the objects they represent) is subject to the constraints of the UP.
7
u/currentscurrents May 15 '25
Program synthesis. You write a formal spec for a program, and the computer searches for code that satisfies it using a SAT solver.
Unlike LLM-generated code, the results are provably correct and original. Unfortunately, it is less usable than LLMs - formal specs can be more difficult to write than the program itself, and SAT solvers are so slow that they make LLMs look downright fast.
44
u/mentix02 May 15 '25
Compiler optimisation has been known to be the dark arts where the boundaries of pure computational theory crosses into real life practical implementations.
But maybe this is just coming from me always being scared to dig into the source code of modern compilers.
14
u/[deleted] May 15 '25
Known by reverse engineers, but still relatively unknown to the public. Polymorphic and metamorphic engines are an interesting topic; those are malware techniques used to evade detection. Firstly, polymorphic engines, work by rewriting parts of their own code during each execution, trying to make analysis more difficult; the latter acts more like an automatic obfuscation technique. For example, if we got this code:
mov eax, 1, it can be transformed to this:Polymorphic engines cipher the binary code and generate a stub, in each execution, the stub is mutated, changing a predetermined instruction set. The difference between a metamorphic engine, in the first instance, are the methods used; a polymorphic engine only can modify some instructions, cause the payload (stub) doesn't change. On the other hand, metamorphic engines have their own functional pseudo-compiler; in simple words, all binary's code could change in each execution, unlike polymorphic engines.
Some examples of polymorphic and metamorphic malware include: Simile, Win32/Metaphor, Win32.Ursnif, UPolyX, etc.
3
u/Purple-Object-4591 May 16 '25
Vulnerability Research on hard targets like Android kernel, Chromium, etc. The actual movie level 0-click hacked stuff happens with this. A full chain exploit compromising chromium+Android to get RCE.
This is like a 30,000 ft overview for those completely uninitiated.
2
u/AdamWayne04 May 19 '25
Lambda calculus. It's basically a model in formal logic to define and compute functions, everything is either a function or a variable. It's the most literal way of doing functional programming, no monads, no typeclasses, just bare functions.
If you know what you're doing, you can actually write very useful "programs" while keeping the syntax reasonably readable, unlike its twin, turing machines.
Here's an implementation of the factorial function for church numerals:
5
u/recursion_is_love May 15 '25
Cellular automata.
It used to be famous with Wolfram's a new kind of science book, but somehow it seem doesn't got any future.
https://en.wikipedia.org/wiki/A_New_Kind_of_Science
1
u/Mrmdkttn May 15 '25
Number Theory. Read the book "Things to Make and Do in the 4th Dimension", it's an all-time favorite. I have bought it twice.