An X-System is a function taking an X-System as input and outputting a boolean. Let X be the set of all such X-Systems
X: X -> Boolean
A T-System is an X-System which outputs true if the input is also a T-System, otherwise it outputs false. Let T be the set of all such T-Systems
T ⊆ X s.t. ∀ t ∈ T, x ∈ X, t(x) = x ∈ T
Question: does any set T of such T-Systems exist? If so, is it non-trivial?
What if we're not dealing with mathematical functions but computational functions? What if they must halt? What if they're impure (i.e. maintain some state between calls)
Some X-Systems are constant: they always output the same value(i.e. they ignore the input). The set of all such systems is B_0
B_0 ⊆ X s.t. ∀ b ∈ B_0, ∃ k s.t. x ∈ X, bo(x) = k B_0 = {(_ => true), (_ => false)}
We can define a transformation, b_0 between a boolean and it's corresponding X-System:
b_0: Boolean -> B_0 b_0(b) = (_ => b)
An inverse transformation is also possible:
b_0': B_0 -> Boolean b_0'(b) = b(x) for some arbitrary x ∈ X
Likewise, we can define a set of X-Systems which take boolean inputs:
B_1 ⊆ X, B_1: B_0 -> Boolean
And transformations between them:
b_1: (Boolean -> Boolean) -> B_1 b_1(f) = (b => f(b_0'(b))) b_1': B_1 -> (Boolean -> Boolean) b_1'(x) = (b => x(b_0(b)))
We can build on this definition to create systems with two inputs
B_2 ⊆ X, B_2: B_1 -> Boolean b_2: (Boolean -> Boolean) -> B_2 b_2(f) = (b => f(b_1'(b))) b_2': B_2 -> (Boolean -> Boolean) b_2'(x) = (b => x(b_1(b)))
We can use induction on the above logic to create systems with an arbitrary number of boolean inputs
B_N ⊆ X, B_N: B_(N-1) -> Boolean b_n: (Boolean -> Boolean -> ...) -> B_N b_n(f) = (b => f(b_(n-1)'(b))) b_n': B_N -> (Boolean -> Boolean -> ...) b_n'(x) = (b => x(b_(n-1)(b)))
A list of booleans (e.g. B_N system inputs) can be transformed into an integer by interpreting them as binary numbers.
We have already seen that we can treat an X-System with multiple boolean inputs as an X-System with an integer input. We can also transform any system with integer inputs to a system with multiple outputs:
toOutput: (Integer -> T) -> (T, T, ...) toOutput(f) = (f(0), f(1), ...)
Using the above logic we can create X-Systems analagous to [Boolean] -> [Boolean]