Since you mentioned Wittgenstein's paradox, I thought someone should explain what that is. Warning: As you suspected, what follows is really philosophy and not mathematics. Nevertheless, it seems worth clarifying what people mean by Wittgenstein's paradox so that you don't go chasing wild geese.
In Wittgenstein's Philosophical Investigations, he makes an argument about "private languages" that Saul Kripke later interpreted in a certain way. The basic point is that it is very difficult, if not impossible, to pin down what a "rule" is. Imagine that you are trying to teach a Martian the syntactic rule, "append a 1 to the end of a string." The Martian looks puzzled so you give some examples:
0 $\to$ 01
101 $\to$ 1011
0010 $\to$ 00101
and so forth. The Martian seems to get the idea, and does a few examples to confirm with you. The first few examples look good, but then all of a sudden the Martian comes up with
1111111 $\to$ 111111110
Say what? Somehow it seems that the Martian hasn't gotten the rule after all. Or maybe the Martian has extrapolated from your examples to a different rule? How do you make sure you communicate the rule you intend? If you have previously already agreed on some basic rules then you can build on those to define new rules, but how do you get started? It's hard to get more basic than "append a 1."
Perhaps you could try building a physical device that optically scans its input and writes a 1 next to it. But any physical device will eventually fail to implement your intended "append a 1" rule when it reaches a certain physical limit, so the device doesn't unambiguously communicate your intended rule to the Martian either.
No matter how you slice it, it seems that you can't guarantee that you have communicated your rule to the Martian, since any finite amount of interaction is consistent with infinitely many rules. Once we see this, we could take a more radical step and wonder, maybe I'm the Martian. Maybe all these years I've been assuming that I know what people mean when they specify syntactic rules, but actually I've just been lucky and haven't discovered the discrepancy between my understanding of what "append a 1" means and what everyone else means by it. (Here you can get a glimpse of where Wittgenstein's term "private language" comes into the discussion.) Even more radically, we could wonder whether the notion of a "rule" is incoherent. Perhaps there really is no such thing as a "rule" in the sense of some unambiguous finite description of something that applies to an infinite number of cases.
Anyway, it is not my intent to start a debate here on MO about this issue, about which many philosophical papers have been written. It is just to confirm that Wittgenstein isn't who you're looking for, if you want a mathematical answer to your question.