4 ms·

In a course on algorithms I took in Moscow State Uni (Russia), we were told there are two ways to describe a Turing machine: - One with a tape & state transiti

by samat 8y ago

In a course on algorithms I took in Moscow State Uni (Russia), we were told there are two ways to describe a Turing machine: - One with a tape & state transition table - A string & a list of string replacements Then we proved this two definitions being equal. And programmed for each ‘system’ a little. I must admit, programming with ‘string replacements’ is much much more fun than doing ‘tape & table’. Is this just some Russian quirk or the same in the West CS courses, too?

schoen 8y ago
I think the other formalism you're talking about is https://en.wikipedia.org/wiki/Markov_algorithm https://en.wikipedia.org/wiki/Markov_algorithm There are a number of different models of universal computation that were formulated in the 1930s or soon afterward and can all be proven to be equivalent in power. In CS courses in the U.S., people might learn about more than one of these and also prove that they're equivalent. But only the one with the tape and symbols is referred to as a "Turing machine" here; the other ones might be called "computation models", "computation formalisms", or something similar. I don't think that the string-rewriting model is as commonly taught over here, although I'm sure it's alluded to in discussions of rewriting in formal grammars https://en.wikipedia.org/wiki/Rewriting https://en.wikipedia.org/wiki/Rewriting Interestingly, the Markov who devised this model of computation is apparently the son of the Markov who studied Markov chains and Markov processes.
- throwawayRO12 8y ago
  You are right. In Romania we also prove that different computational models are equivalent (Turing machine, lambda calculus, Markov machine, logic programming)
  - abhishekjha 8y ago
    >prove that different computational models are equivalent (Turing machine, lambda calculus, Markov machine, logic programming) Is there a text which guides how to write such a proof?
    - naniwaduni 8y ago
      Generally, implement/simulate one in the other.
    - theonemind 8y ago
      i remember covering this sort of thing in my automata theory class. we used this textbook: https://www.amazon.com/Automata-Computability-Complexity-Theory-Applications/dp/0132288060 https://www.amazon.com/Automata-Computability-Complexity-The... I can't remember if it specifically shows such a proof in there, but you might look at courseware for automata theory and such. In general, from what I remember, you would use a general technique called "reduction", where you try to make two problems equivalent, "reducing" solving one to the problem of solving the other one, kind of mapping one problem on to another, so that solving one solves them both. So, you reduce running an arbitrary Turing machine, to say, lambda calculus, almost like you write a "compiler" from a Turing machine with lambda calculus as the target language. Then, you reduce computing in lambda calculus to a Turing machine. So, then you know that each can compute what the other computes, and they can only compute the same things. If you only did one half, one reduction, you would only know, say, that a Turing machine could do everything you could do in lambda calculus, but it would leave the possibility that the Turing machine could compute things lambda calculus can't.
Cu3PO42 8y ago
In my formal languages course in Germany we covered various computational models and showed the equivalences to Turing Machines. We never built complex TMs by hand, only describing how they would work. I did, however, build larger TMs by hand in a high school course.
- gnulinux 8y ago
  Uh in a logic class, I had to build a really large TM that computes the Collatz Function (3n+1 or //2 depending on arity) and it was a very menial task. To debug my TM, I built a simple TM smulator in python and wrote unittests.
lqet 8y ago
> Is this just some Russian quirk or the same in the West CS courses, too? I spent months building TMs (also a lot of DFAs) and equivalents as an undergraduate student (which was a lot of fun), and personally I always thought of a TM as a string character replacement machine. The set of alphabet symbols for a TM is of course not restricted to {0, 1}, you can also chose all UTF-8 characters if you like.
agumonkey 8y ago
my brain always preferred rewriting systems to naive TM interpretation anybody else ?
porpoisely 8y ago
We learn this in our Theory of Computation classes. Starting with basic deterministic finite automata to nondeterministic to regular languages to context free grammars to pushdown automatas to turing machines and halting problem.

by samat 8y ago

schoen 8y ago

I think the other formalism you're talking about is https://en.wikipedia.org/wiki/Markov_algorithm https://en.wikipedia.org/wiki/Markov_algorithm There are a number of different models of universal computation that were formulated in the 1930s or soon afterward and can all be proven to be equivalent in power. In CS courses in the U.S., people might learn about more than one of these and also prove that they're equivalent. But only the one with the tape and symbols is referred to as a "Turing machine" here; the other ones might be called "computation models", "computation formalisms", or something similar. I don't think that the string-rewriting model is as commonly taught over here, although I'm sure it's alluded to in discussions of rewriting in formal grammars https://en.wikipedia.org/wiki/Rewriting https://en.wikipedia.org/wiki/Rewriting Interestingly, the Markov who devised this model of computation is apparently the son of the Markov who studied Markov chains and Markov processes.

throwawayRO12 8y ago
You are right. In Romania we also prove that different computational models are equivalent (Turing machine, lambda calculus, Markov machine, logic programming)
- abhishekjha 8y ago
  >prove that different computational models are equivalent (Turing machine, lambda calculus, Markov machine, logic programming) Is there a text which guides how to write such a proof?
  - naniwaduni 8y ago
    Generally, implement/simulate one in the other.
  - theonemind 8y ago
    i remember covering this sort of thing in my automata theory class. we used this textbook: https://www.amazon.com/Automata-Computability-Complexity-Theory-Applications/dp/0132288060 https://www.amazon.com/Automata-Computability-Complexity-The... I can't remember if it specifically shows such a proof in there, but you might look at courseware for automata theory and such. In general, from what I remember, you would use a general technique called "reduction", where you try to make two problems equivalent, "reducing" solving one to the problem of solving the other one, kind of mapping one problem on to another, so that solving one solves them both. So, you reduce running an arbitrary Turing machine, to say, lambda calculus, almost like you write a "compiler" from a Turing machine with lambda calculus as the target language. Then, you reduce computing in lambda calculus to a Turing machine. So, then you know that each can compute what the other computes, and they can only compute the same things. If you only did one half, one reduction, you would only know, say, that a Turing machine could do everything you could do in lambda calculus, but it would leave the possibility that the Turing machine could compute things lambda calculus can't.

Cu3PO42 8y ago

In my formal languages course in Germany we covered various computational models and showed the equivalences to Turing Machines. We never built complex TMs by hand, only describing how they would work. I did, however, build larger TMs by hand in a high school course.

gnulinux 8y ago
Uh in a logic class, I had to build a really large TM that computes the Collatz Function (3n+1 or //2 depending on arity) and it was a very menial task. To debug my TM, I built a simple TM smulator in python and wrote unittests.

lqet 8y ago

> Is this just some Russian quirk or the same in the West CS courses, too? I spent months building TMs (also a lot of DFAs) and equivalents as an undergraduate student (which was a lot of fun), and personally I always thought of a TM as a string character replacement machine. The set of alphabet symbols for a TM is of course not restricted to {0, 1}, you can also chose all UTF-8 characters if you like.

agumonkey 8y ago

my brain always preferred rewriting systems to naive TM interpretation anybody else ?

porpoisely 8y ago

We learn this in our Theory of Computation classes. Starting with basic deterministic finite automata to nondeterministic to regular languages to context free grammars to pushdown automatas to turing machines and halting problem.