Σ∞

Σ∞, stylized as Σ_∞ is an uncomputable esoteric programming language with the goal of being extremely powerful; beyond Turing completeness. Specifically, there are two versions: Version 0 and Version 1, with the goal of having strength as Σ⁰_∞ and Σ¹_∞ in the arithmetic and analytical hierarchy respectively. We can denote them as Σ∞0 and Σ∞1. Both versions are total because all expressions necessarily have a value, but it may require performing hypercomputations.

Version 0

In Version 0, our universe consists of the nonnegative integers augmented with the constant ∞. Specifically, our universe is ℕ ∪ {∞}. The way ∞ works is through this rule:

x + ∞ = ∞ + x = ∞

A valid Σ∞ program is done through these production rules:

P ::= ∞ | V | Σ[P≤V<P]P
V ::= (a string of lowercase alphabetic characters)

Here, P represents a program string and V represents a variable. Indeed, all variables are either bounded to a Σ or are free variables used for inputs.

Interpreting the program

The way programs are evaluated goes like this:

∞ is just infinity
Σ[A≤x<B]C(x) is just the sum of C(x) for all integers x greater than or equal to A, and less than B. 
Here, C(i) is just C(x) but all instances of variable x replaced with i.
The sum may output infinity if the summation diverges or if at least one of the intermediate C(i) is infinite. 
By default, the empty sum outputs zero.

For example, `Σ[∞≤x<∞]∞` = 0 because there are no natural numbers greater than or equal to infinity. Then `Σ[Σ[∞≤x<∞]∞≤y<∞]F(x)` = F(0)+F(1)+F(2)+...

Inputs and outputs

Sometimes the program might take in multiple numbers as inputs. These are loaded into free variables in shortlex order (a, b, c, ..., z, aa, ab, ...). The output is the result of interpreting the program.

Version 1

This version makes Σ∞ significantly stronger by adding real numbers.

Σℝ[A≤x<B]C now sum over all real numbers in the interval [A,B). Note that if A=B then the result is the empty sum.

The traditional summation Σℕ[A≤x<B]C still works. One big thing is we never add negative real numbers, so summations either converge or diverge absolutely. This means we do not have to worry in what order numbers are added.

Computational Class

To check the computational class, let's try to build simple constructs.

0 := Σ[∞≤a<∞]∞
x(x-1)/2 := Σ[0≤a<x]a
1 := Σ[0≤a<∞]Σ[Σ[0≤c<a]c≤b<a]b
NOT(x) = Σ[x≤a<∞]∞
IS_POSITIVE(x) = Σ[0≤a<∞]x
AND(x,y) = MULTIPLY(x,y) = Σ[0≤a<x]y
OR(x,y) = NOT(AND(NOT(x),NOT(y))) (probably easier way)
LESS(x,y) = Σ[x≤a<y]∞
GTEQ(x,y) = NOT(LESS(x,y))
EQUAL(x,y) = AND(GTEQ(x,y),GTEQ(y,x))
INDICATOR(x) = Σ[0≤a<x]Σ[Σ[0≤c<a]c≤b<a]b (returns 1 if x=inf, 0 if x=0)
ADD(x,y) = Σ[0≤a<∞]Σ[0≤b<∞]INDICATOR(OR(AND(EQUAL(a,0),LESS(b,x)),AND(EQUAL(a,1),LESS(b,y))))
THERE_EXISTS(P) = Σ[0≤x<∞]P(x)

Here, we use ∞ as TRUE and 0 as FALSE for Booleans, and INDICATOR(x) turns that into a 1/0 output. The above should be enough to simulate first order arithmetic, which means that Version 0 can simulate anything expressible in the arithmetic hierarchy.

We can express any computable function by counting solutions in an exponential diophantine equation:

Σ[0≤a<∞]Σ[0≤b<∞]Σ[0≤c<∞]...Σ[0≤k<∞]INDICATOR(EQUAL(P(a,2^a,b,2^b,...k,2^k),Q(a,2^a,b,2^b,...k,2^k)))

Exponentiation can use a beta function.

Version 1

Adding Σℝ allows us to quantify over sets of natural numbers. Specifically, we can encode a set as a base 4 string b₀.b₁b₂b₃b₄..., where b_i=2 if our set contains the number i, and b_i=0 otherwise.

We can check if a particular number belongs to a set by multiply by 4ⁱ, taking the floor by counting number of smaller natural numbers, and modulo by 4. Since Σℝ can quantify over sets of natural numbers encoded as reals, Version 1 can express any second order arithmetic statement, or anything in the analytical hierarchy.