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 ?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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).

Improve this answer
$\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$ 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$ 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$ 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 .

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.