News for hackers. Stuff that matters.
Re:A proof that Unix utility sed is Turing complete by samat on Friday February 15, 2019 @01:17AM (#19168857)
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?

Re:A proof that Unix utility sed is Turing complete by schoen on Friday February 15, 2019 @02:01AM (#19169008)
I think the other formalism you're talking about is

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

Interestingly, the Markov who devised this model of computation is apparently the son of the Markov who studied Markov chains and Markov processes.

Re:A proof that Unix utility sed is Turing complete by throwawayRO12 on Friday February 15, 2019 @02:10AM (#19169051)
You are right. In Romania we also prove that different computational models are equivalent (Turing machine, lambda calculus, Markov machine, logic programming)
Re:A proof that Unix utility sed is Turing complete by abhishekjha on Friday February 15, 2019 @06:31AM (#19170040)
>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?

Re:A proof that Unix utility sed is Turing complete by theonemind on Friday February 15, 2019 @01:36PM (#19173452)
i remember covering this sort of thing in my automata theory class. we used this textbook: 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.

Re:A proof that Unix utility sed is Turing complete by naniwaduni on Friday February 15, 2019 @06:41AM (#19170081)
Generally, implement/simulate one in the other.
Re:A proof that Unix utility sed is Turing complete by Cu3PO42 on Friday February 15, 2019 @02:37AM (#19169168)
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.

Re:A proof that Unix utility sed is Turing complete by gnulinux on Friday February 15, 2019 @09:31AM (#19171160)
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.
Re:A proof that Unix utility sed is Turing complete by lqet on Friday February 15, 2019 @04:41AM (#19169633)
> 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.

Re:A proof that Unix utility sed is Turing complete by agumonkey on Friday February 15, 2019 @07:14AM (#19170221)
my brain always preferred rewriting systems to naive TM interpretation

anybody else ?

Re:A proof that Unix utility sed is Turing complete by porpoisely on Friday February 15, 2019 @02:46PM (#19174077)
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.