Cheap and Secure Web Hosting Provider : See Now

# Is modulus capable of universal computation?

, ,
Problem Detail:

I heard once that you could translate any digital circuit into a modulus operation, perhaps modulusing against different numbers?

It was a long while ago though and don't remember where I heard it.

Is this true or does it ring any bells?

###### Answered By : Yuval Filmus

You have to distinguish between two meanings of computation:

1. Computation of functions on a finite domain (e.g. circuits).

2. Computation of functions on an infinite domain (e.g. Turing machines).

A single division operation cannot be universal in terms of the second meaning, since division is total: it always halts (even division by zero halts). However, it could possibly be universal in terms of the first meaning. For example, if we encode the input using different primes, then the Chinese Remainder Theorem shows that $x \mapsto n \pmod{x}$ is universal, that is, for every Boolean function $f$ on some set $S$ of finite primes there is a number $n$ such that for every $x \in S$, $n \mod{x} = f(x)$.