2
$\begingroup$

Given a finite alphabet $\Sigma$. We define the set of all words of finite length to be $\Sigma^{*}$.

A partial function can become a total function with trivial modifications, thus we just consider about the total function.

Is the following definition correct?

We say a function $f \colon \Sigma^{*} \rightarrow \Sigma^{*}$ is computable by a NDTM $M$, if $M$ halts on every input $x \in \Sigma^{*}$ and The run of $M$ on $x$ halts with $f(x)$ written on its tape.

My questions:

1-What is the usefulness of $q_{accept}$ and $q_{reject}$ here？What kind of inputs dose the $M$ accept (reject)?

2-Is the output of the $M$ are the same on input $x$? (the NDTM may choose different transition functions)

3-Do we need require that all branches halt for $M(x)=1$?

Finally, how can we use this definition to solve a function problem or a search problem?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Seems to me you could profit from a look into a textbook. $\endgroup$
    – Raphael
    Commented Oct 5, 2017 at 20:31
  • 1
    $\begingroup$ There are several different definitions, they may be equivalent, but they make me confused, and some books don't introduce the details about it since it is similar to the related concepts of TM. $\endgroup$
    – Blanco
    Commented Oct 5, 2017 at 20:38
  • 2
    $\begingroup$ Your definition works for deterministic Turing machines. Nondeterministic machines work differently. We don't usually consider functions computed by nondeterministic machines, though appropriate definitions are around; rather, we consider predicates. $\endgroup$
    – Yuval Filmus
    Commented Oct 7, 2017 at 10:38
  • $\begingroup$ That means we cannot use a NDTM to solve a function problem or a search problem? @YuvalFilmus $\endgroup$
    – Blanco
    Commented Oct 7, 2017 at 17:27
  • $\begingroup$ @TeamBright There are too many possible definitions for a NDTM computing a function, with no clear "winner". With predicates, the result is boolean, and combining many such boolean results is done using OR. (AND is another reasonable choice, albeit leading to a different notion.) With arbitrary outputs, instead of boolean ones, there are too many ways to combine the multiple results into a single one. $\endgroup$
    – chi
    Commented Oct 7, 2017 at 18:51

1 Answer 1

Reset to default
2
$\begingroup$

One should not confuse function problems like FNP and FP with the different types of functions computable by deterministic, non-deterministic, alternating, probabilistic, or ... Turing machines.

Instead of starting by looking at functions $f:\Sigma^* \to \Sigma^*$, it is easier to start by looking at functions $f:\Sigma^* \to \mathcal{P}(\Sigma^*)$. A function $f:X\to\mathcal{P}(Y)$ is equivalent with to a subset $R\subset X\times Y$ of the cartesian product of $X$ and $Y$, i.e. to a binary relation.

Since we can assume that the decision problem is already defined, using the decision problem for $R$ gives one reasonable definition for the computable functions (of this form). However, that definition would force the different Turing machines to compute each output-bit separately and independently, which is a small speed penalty. One can allow the different machines to produce the output in a way more suitable to their capabilities, to avoid that penalty.

The more annoying problem is that the form of output is different from the form of input. One could combine that with a stupid translation function $g:S\to \Sigma^*$ for $S\subset \mathcal{P}(\Sigma^*)$ to bring the output into the same form as the input. But if the output was produced in a way more suitable to the different capabilities of the Turing machines, such a stupid translation function might need to be more powerful than desired. Even accepting the small speed penalty would not allow to avoid that problem, since the functions computable by the different Turing machines are often not closed under composition. That problem might be partly solved by using monads (and accepting $\mathcal{P}(\Sigma^*)$ as the form of output), but then the fact that functions computable by deterministic or alternating Turing machines were actually closed under composition gets hidden.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'm not sure that I got your point. You mean that we should define a function $f \colon \Sigma^{*} \mapsto \mathcal{P}(\Sigma^{*})$ is computable by a NDTM. If we want to solve a function problem $h \colon \Sigma^{*} \mapsto \Sigma^{*}$, we can choose a translation $g \colon \mathcal{P} (\Sigma^{*}) \supset S \mapsto \Sigma^{*}$ at first. Then we can define that a NDTM can solve $h$ if there exists a computable function $f$ such that $h = g \circ f$. Is that right? $\endgroup$
    – Blanco
    Commented Oct 12, 2017 at 18:18
  • $\begingroup$ Or $h = g \circ (f_{1}f_{2} \cdots f_{m})$ and the latter may be more powerful than former if the computable functions are not closed under the composition operation, where $\circ$ is the compound operation and $f_{1}f_{2}$ is the composition operation. $\endgroup$
    – Blanco
    Commented Oct 12, 2017 at 18:42

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.