3
$\begingroup$

An algorithm on an abstract machine is a finite sequence of operations of the machine. (Correct me if I am not correct.)

However, there are different kind of algorithms, such as deterministic, non-deterministic, and randomized algorithms, and possibly others.

Are these algorithms running on deterministic Turing Machines, or do they have to be run on specific machines? For example:

  1. Are nondeterministic algorithm algorithms on a deterministic Turing machine? I heard that they are not, but are on nondeterminisitic Turing machines, but I forget where I heard it. Or I might be wrong.
  2. Are randomized algorithms algorithms on a deterministic Turing machine?
$\endgroup$
  • $\begingroup$ Non-deterministic turning machines are equivalent to deterministic ones. And a turning machine can implement any algorithm. Basically it does not matter if it's DTM or NTM. $\endgroup$ – Spencer Wieczorek Nov 1 '14 at 1:06
1
$\begingroup$

Broadly speaking, you can normally trade the word "algorithm" for the words "Turing Machine", in the sense that a Turing Machine is not a programmable computer like the one you have in front of you, it is a mathematical embodiment of an algorithm. So for the two cases you mention:

  1. A nondeterministic algorithm is a nondeterministic Turing Machine.
  2. A randomized algorithm is a probabilistic Turing Machine.
$\endgroup$
  • $\begingroup$ I like this line of thinking. A Turing "machine" is a program in a language we have formal semantics for. There is no machine, really; the usual cost measures are defined in terms of the semantics. That said, a universal TM is a machine in the "programmable computer" sense. And an algorithm. $\endgroup$ – Raphael Apr 8 '15 at 10:52
  • $\begingroup$ @Raphael You cannot escape this line of thinking as soon as you try to answer the question. That is why it is a good question. $\endgroup$ – babou Apr 8 '15 at 11:41
  • $\begingroup$ @Raphael, I like the duality as well, a programmable computer is really just an algorithm too. The input just happens to be the description of another algorithm. $\endgroup$ – Luke Mathieson Apr 9 '15 at 0:41
1
$\begingroup$

In a nutshell: A Turing Machine is an algorithm by itself, not a programmable device. However, deterministics, non-deterministic, or randomized algorithms can be interpreted on universal deterministic TM. However, this does raise some problems in the case of randomized algorithms.

I can see the intent of your question, that could be a good one but is not quite well stated. But then it is an opportunity to look at things more precisely. This answer is in agreement with Luke Mathieson's answer, and trying to understand further what motivates the question.

The problem is that you do not program Turing Machines (TM). TMs are not programmable machines, they are just the transition function described by their definition. A TM will do the computation it is intended for an no other.

So, a TM is not a programmable machine. It can at best be considered as belonging to an abstract machine model. This is actually generally true in automata theory. A PushDown Automaton (PDA) is a specific PDA that recognizes only one context-free language.

You may want to see them an abstract machine models with a program running them, but that is not the way theory does it. So, for all purpose and intent, the program is the machine in the theoretical framework, i.e. the algorithm is the machine. This is essentially the answer given by Luke Mathieson.

This seems to remain an unsaid misunderstanding, though. People should talk of running an algorithm as a Turing Machine, and not on a Turing Machine. But a check with a search engine (Google) gives only one answer for the former ("run as a Turing Machine"), but gives 13000 answers for the latter ("run on a Turing Machine").

Now, you may have various kinds of simulations in this context. For example, you can show that for each machine of type A there is a machine of type B that computes exactly the same result.

You can also have so called Universal Machines. A universal machine U can take as input the description (encoding) of another machine A together with a description of its inputs I, and mimics the computation on A on the input I. The better known ones are the Universal Turing Machines, and also the classical computer. A more common name for it is an interpreter.

An interpreter is the kind of machine on which you run a program, an algorithm description. I would say it is the only kind for which you question makes sense.

The difficulty then is to understand what sense the question can make. The problem is that an algorithm may be seen with various intended meanings. For example, the meaning can just be the language it defines, or enumerate. It can also be how it does it. The computational cost of the algorithm may or may not be part of what you are interested in, of what you want to see preserved by the simulation. So the issue is whether the interpreter you are using is or is not capable of simulating the algorithm in a way that gives you a precise account of what you consider of interest in the algorithm computation.

Non deterministic algorithms can be interpreted in various ways on deterministic interpreter. For practical uses, on of the early attempts to do that is due to Robert Floyd's "Non-deterministic algorithms" in 1966.

General context-free parsers can also be viewed as interpretation of non-deterministic PDA on deterministic machines.

Randomized algorithms are also usually interpreted on deterministic machines, using (pseudo) random number generators.

However, Traduttore, traditore, running these algorithms on a deterministic interpreter may give only a specific vision, an approximation, of what these algorithms do. But the situation is not quite the same for non-deterministic and for randomized algorithms.

In the case of a non deterministic algorithm, the deterministic simulation, for example with breadth first search of an answer, may lose the spirit of non-determinism, of the computational model, but it gives something that is computationally equivalent. If you choose to view non-deterministic choice as being oracle based, it gives you an implementation of the oracle.

Of course, without going into details, another possibility is to interpret a non deterministic algorithm on a non-deterministic universal machine. I do not know how useful that can be.

In the case of randomized algorithm, things are different. Simulation on a deterministic machine require the use of a random number generator. But, all a deterministic machine can provide is a pseudo random number generator, which is actually a deterministic algorithm. So deterministic simulation is intrinsically different from a true probabilistic Turing Machine, and may raise issues regarding the "real" randomness of the generator. My guess, but this would require double checking with experts, is that a true probabilistic TM can produce a non-computable number, while a deterministic simulation cannot do that. But does it matter much?

It is however possible to consider abstractedly that the interpreter has a true random number generator, which is equivalent to using a probabilistic universal machine as interpreter. Concretely, on a real interpreting machine such as a computer, that amounts to assuming the random number generator can be trusted, or to using as a random number generator a physical phenomenon considered "truly" random.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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