World's most popular travel blog for travel bloggers.

Is modulus capable of universal computation?

, , No Comments
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?

Asked By : Alan Wolfe
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)$.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback