Ignoring secondary concerns like usefulness and performance, it's surprisingly easy to create languages that can express all kinds of complex computations and the machines to carry them out.
Pattern Substitutions can be used to perform non-trivial math and (with enough patience) many more kinds of computations.
By repeatedly running a query in the Neo4j graph database, we can efficiently count the paths between two nodes in a 2D grid-graph by storing intermediate results in the nodes.
My Compiler from a Scheme-dialect to LLVM-IR without garbage collection can still compile itself given enough RAM.
In EulerLisp a lot of the heavy lifting is done by code written in Rust. Once it was powerful enough to solve the first Project Euler , it did not take many more features to implement solutions for the next hundred problems.