Compute machine more powerful than Turing Machine

In this article, we describe a type of machine with more compute power than a Turing Machine.

Function definitions in most programming languages are compressed definitions. In other words, they are like syntax sugars.

Hypothetically, we have a type of machine called Machine Z that can turn the two functions below…

fn invert_1(x: bool) -> bool {
  if x == true {
    false
  } else {
    true
  }
}

fn invert_2(x: bool) -> bool {
  if x == false {
    true
  } else {
    false
  }
}

… into the mapping …

true -> false
false -> true

Then we say that invert_1 and invert_2 are definitionally equal, even though their notations in Rust are different.

In Machine Z, a function with type $A -> B$ is a set of paths¹, where, for all terms of $A$ ($a$), there exist a path whose start is $a$ and whose end is a term of $B$.

By this definition, how a function is described can be “compiled” into a mapping (a set of paths). To “apply a function”, is to apply the path with the function input as the path’s start.

noncomputable in Lean means “cannot be computed in a Turing Machine”, but some such functions can be computed in Machine Z.
Correction: noncomputable tells the Lean compiler to skip code generation for that function. You can mark any function as noncomputable if you want. Functions like Real.sqrt involve infinite structure and is not total under Lean. However, Machine Z would be able to compute it.

In Machine Z, for any two functions of the same type, it’s possible to test if they are equal by reducing their description to mapping and compare the two mappings.

In Lean, it is easier to compute (sqrt 2) * (sqrt 2) by first proving (sqrt x) * (sqrt x) = x then applying the equation over the left expression. In Machine Z, you can just evaluate the two numbers and multiply them.

Programming is like playing with algebra. Since our Turing Machine cannot reduce function definitions into direct mappings (lookup table), it applies the function based on how it is written (its AST and transformed code from the AST).

I suspect humans may have more complexity than a Turing Machine.

Two functions of the same type, whether they came from defined rules or learned by itself, reduce to a mapping. The mapping doesn’t care about where it comes from, whether it comes from first principles or is learned from experience. Computationally, it might be hard to differentiate a machine learning model from a function described by AST.

Prior art

The above use terms that I invented, not the computer science standard. The below use standard terms in literature.

“Machine Z” is not a machine in the traditional sense; it is an oracle. It does not “compute” the result. It “sees”.

Machine Z is a hypercomputer.

No resource bound -> no complexity class.

Turing degree: I don’t quite understand this, but either Machine Z can solve halting, or it can only reduce total functions to their mapping.

Restriction about our universe: the strongest computing model physics has given us, the quantum computer, computes BQP, which sits below PP (proved as BQP ⊆ AWPP ⊆ PP, Fortnow–Rogers), so it is still Turing-computable. What is assumed from experiment, not proved, is that our universe realizes BQP at all; no physical system has been shown to compute beyond a Turing Machine, so no physical system has been shown to be a Machine Z.

Main reason of BQP ⊆ PP: If you have a branching algorithm with multiple possible outputs, you can rather spend time sampling it (1 run -> 1 random outcome), or you can spend memory caching intermediate results. Machine Z has no concept of time (it has no resource bound).