0
$\begingroup$

Given a function like:

f(x) = x=y then 1 else 0

The number y is a natural number, other than that is unknown

I had two approaches in mind:

  • The function is computable since an algorithm exists, that can compare two numbers, and tell whether they are equal return 1, otherwise 0.

  • The function is not computable, since we would need to know the number y to write an algorithm that compares the numbers.

Can someone give me a hint into the right direction?

$\endgroup$
2
  • $\begingroup$ Your question is ambiguous: "we would need to know the number": which one ? $\endgroup$
    – user16034
    Jun 25, 2023 at 14:31
  • $\begingroup$ If $y$ is unknown but natural, then the function $f$ tells if $x$ is natural. But calculability deals with natural numbers, so the function value is always $1$. $\endgroup$
    – user16034
    Jun 25, 2023 at 14:32

1 Answer 1

1
$\begingroup$

A common definition of a computable function $f(x) : \mathcal{X} \to \mathbb{N}$ is as follows:

There exists a Turing machine that given $x\in \mathcal{X}$ on its initial tape will produce $f(x)$ after a finite amount of steps.

Note that it only requires such a Turing machine to exist.

Now for your question, we can produce an infinite set of Turing machines by mapping each natural number $y$ to a Turing machine that tests if its input $x$ equals $y$. Each of these Turing machines obviously exists. Since your function $f$ is equivalent to one of these Turing machines, it must be computable.

$\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.