1
$\begingroup$

Lets say we need a function to add two numbers and another function to multiply two numbers.

To take a trivial example, consider the function $F(a, b, c, d) = a \cdot (c+d) + b \cdot (c\cdot d)$ If $a=1$ and $b=0$, then $F$ adds $c$ and $d$. If $a=0$ and $b=1$, then $F$ multiplies $c$ and $d$.

So to evaluate both add and mult I can have only one function $F$ with variable inputs.

Can we have a general function that can evaluate any arbitrary function ? of course with an upper bound on the complexity ? If yes how do we prove in theory that such a general function is possible ? What is this called in theory ?

$\endgroup$

2 Answers 2

5
$\begingroup$

The function you are describing is known as a universal Turing machine. A universal Turing machine is given a Turing machine $T$ and an input $x$, and outputs $T(x)$ (if $T$ doesn't halt, the universal Turing machine also doesn't halt).

If you want your function to have restricted complexity, you can just stop the computation once it has gone on for too long, and output zero, say. For any Turing machine with the correct complexity, the restricted universal Turing machine will still be correct. A variant is to accept a clocked Turing machine, which provides its own bound on the running time (which you can choose to ignore at your discretion).

$\endgroup$
4
  • $\begingroup$ Oh yeah thanks ! am curious, how does this work in practice ? i see that UTM is all in theory. in reality how do i write such function $\endgroup$
    – sashank
    Commented May 7, 2013 at 18:23
  • 2
    $\begingroup$ In practice, a universal Turing machine is called a computer, and its input is called code. $\endgroup$
    – JeffE
    Commented May 7, 2013 at 18:51
  • $\begingroup$ i did not get it , in my question, how do i write the function F ? that can evaluate any function $\endgroup$
    – sashank
    Commented May 8, 2013 at 0:38
  • $\begingroup$ In practice, the function $F$ is called a compiler or an interpreter. $\endgroup$ Commented May 8, 2013 at 13:36
1
$\begingroup$

"Universal Boolean Function" is what i was looking for .

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.