[JTHM]

Does anyone know how a non-deterministic Turing machine solves function problems? I understand how it solves decision problems (if any branch of the computation reaches an accept state, the machine accepts), but how does it solve problems for which it is required to give an output? Is there a separate output tape that any branch of the computation can write on? What happens if two different branches of the computation try to write different things on that tape? Or does each branch of the computation have its own output tape? If so, what happens when two different branches try to give two different answers to the problem at the same time?

[mojo666]

This should help. NTMs Equivalence with DTMs

One way of doing this is to try a path, if it fails go back and try another

[blackcompe]

A decision problem is simply one with a yes or no answer. An FSM doing regex matching or LR parsing solves a decision problem. The match was found or it wasn't; the sentence is syntactically correct or it isn't.

Quote

For all function problems in which the solution is polynomially bounded, there is an analogous decision problem such that the function problem can be solved by polynomial-time Turing reduction to that decision problem. For example, the decision problem analogue to the travelling salesman problem is this:

Given a weighted directed graph and an integer K, is there a Hamilton path (or Hamilton cycle if the salesman must return home) with total weight less than or equal to K?

~ Function Problem

That's one way to prove an FSM solves function problems too (through reductions).

This post has been edited by blackcompe: 25 April 2012 - 03:50 PM

[sepp2k]

A non-deterministic Turing machine will simply not produce a single output, but a set of outputs. One could say that a NDTM solves a function problem if each path that results in an accepting state produces a valid solution as its output or that it solves the problem if at least one path produces a valid solution as its output.

I don't know whether there is an "official" definition or which one of these two would be it.

This post has been edited by sepp2k: 26 April 2012 - 12:48 AM

[Nikitin]

Each branch can have it's own output tape. This is equivalent to having a single tape, shared by all other branches. For example, when the branch 'N' wants to output the character 'X', it would put the character 'NX' onto the output tape, encoded in some way.

Whenever some branch found the answer, it can put a special character at the end of the output tape to signify a halt, also putting its branch ID. Any other branches may halt as well, when they see that they're trying to append to that special character.

The output of the answer branch can then be easily collected.