A proof that Unix utility sed is Turing complete
catonmat.net
catonmat.net
- 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?
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.
Is there a text which guides how to write such a proof?
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.
I did, however, build larger TMs by hand in a high school course.
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.
anybody else ?
Would be interesting to see e.g. how fast Microsoft Word runs on a sed based backend.
[1] https://en.wikipedia.org/wiki/Interactive_computation (or course I use the term Interactive TMs a bit loosely, but y'know...)
In other words, if sed is turing complete, this means you could run any other turing complete program on it.
Producing a GUI is also just telling your CPU (a sophisticated turing machine) to format data and how to send the formated data to a display.
EDIT: what justifies the downvotes? Sure the display is not part of the turing machine, but the display is also not part of the GUI. The GUI is a software component that can be created by a turing machine. You wouldn't disagree with me for stating a GUI can be created through a C or Java program.
You can change the definition and add those devices, or you can simulate those devices on your tape, but simulation is not reality.
I'm not saying it's easy, efficient or even desirable to do so, but if sed is turing complete this means we could write a compiler to run any other turing complete program on it. That this process might need basically recompiling a whole operating system might be true, but it doesn't contradict the theory.
I don't understand the downvotes here. I might very well be wrong, but your answer isn't giving an explanation for that.
One turing machine can write to a certain position on a tape, while another turing machine can read from that position on the tape. At that point we communicated between two turing machines. Add some electric engineering to allow this tape position to send electrical signals from one place to another other a wire and you have peripheral devices. Yes actually displaying something through a display is thus more than a turing machine.
But the topic at hand was between the different capabilities of one turing complete program/language (Word) and another turing complete program/language (sed) executing on the same turing machine. The definition of turing complete is that anything the first program can do, the second can do too.
at that point we are only speaking about access control. It's very well possible to run sed in a context, so the bytes it outputs can be used to display information. In fact that's exactly what the console does. It interprets the output of sed as text and displays it on the screen. Nothing forces you to display the sed output in a console.
Digital displays only get bytes as input and output visible light for humans. These bytes are mostly an arbitrary format optimized for performance. Sed can output arbitrary bytes too based on an input program. That's what "sed is turing complete" tells us.
That’s the entire point. sed cannot run Microsoft Word because it cannot control the hardware in the right way. Sure, you could hook up sed to do this, but that would be kind of stupid and useful only in a purely academic sense.
Turing-complete just means that it can compute any function that a Turing machine can compute. Turing machines are universal computers, not universal machines.
My computer can compute F ⇒ a Turing machine can compute F (assuming the Church-Turing thesis).
My computer can do X ⇏ a Turing machine can do X.
I'd also note that because physical computers have finite storage, you could by the same logic implement Word in a finite-state machine. You could implement the transitions of a finite-state machine using symbolic links in the filesystem. With enough of a surrounding framework, ls -l could be used to do transitions between machine states and drive the program.
So you can write Word in ls in the same way you can write it in sed.
In fact it does. That's the whole point of turing-completeness. It is actually possible to create output with sed that results in executable bytecode similar to C. You would need a sed to bytecode compiler. You could even write this compiler in sed (once you have something else that can compile sed). Why? Because sed is turing complete. Yes, it's very unpractical to do so, but you could do it even on current hardware.
> I'd also note that because physical computers have finite storage, you could by the same logic implement Word in a finite-state machine.
actually you can't. Word itself is turing complete, i.e. you can theoretically program with Word. So no you can't implement word with a finite-state machine, because it can't reflect the theoretically infinite states an arbitrary input program can create. You need a turing machine for that.
> So you can write Word in ls in the same way you can write it in sed.
No. That's missing the point of sed being turing complete.
The executable bytecode for Word is a constant. cat can output that.
> Word itself is turing complete
Word on a physical computer doesn't have access to an infinite tape. It can only reach a finite number of states, so you can simulate Word as run on a physical machine using a finite state machine with perfect fidelity.
>> It is actually possible to create output with sed that results in executable bytecode similar to C.
> The executable bytecode for Word is a constant. cat can output that.
I didn't mean output in the sense of printing it to a screen. What I wanted to say is that you can write anything in sed that you can write in C and that you could create a compiler for sed like you can create a C compiler, to run arbitary sed programs on current hardware.
>> Word itself is turing complete
> Word on a physical computer doesn't have access to an infinite tape. It can only reach a finite number of states, so you can simulate Word as run on a physical machine using a finite state machine with perfect fidelity.
No, I'm pretty sure you can't. A finite-state machines can not even parse context-free (Chomsky type-2) languages, so it definitely can not execute a general purpose program written in Word, even with a finite amount of memory. And as we can write general purpose programs in Word (and in sed, because they are both turing complete), you could never create a finite-state machine that can do everything that Word can do.
But yes, we usually ignore that our computers don't have infinite tape, as even the possible permutations for input programs of just 1kb are for our purposes basically endless (2^1024).
The point with C, C++, Java, Python, Word and sed being turing complete is that you can write general purpose programs for them to execute. You can not write general purpose programs for finite-state machines, you can not even create finite-state machines for every program. That's the interesting part of identifying if something is turing complete, even though it has no practical use it's not, because there isn't the necessary envrionment and it's never as efficient as the general purpose programming languages we built.
This actually doesn't follow from sed being Turing-complete, and I don't think it's true. The construction to show that sed is Turing-complete requires transforming the input into one that sed can then perform computations on. I think a more clear example is Lambda calculus.
You can't write a Lambda calculus expression that increments a binary number. Lambda calculus can only operate on lambda expressions. Turing-completeness just means it's capable of computing the same sort of functions, not that it can match the input and output formats.
> you could create a compiler for sed like you can create a C compiler, to run arbitary sed programs on current hardware.
My point is that no input to sed will result in a Word window opening. sed can perform all the same calculations, but there's more to Word than that. I think we're agreed on this point. We're also agreed that you could embed sed in an appropriate framework and produce that window. I think our disagreement between these is mostly semantics, so I'm happy to stop arguing about it if you're done.
> No, I'm pretty sure you can't. A finite-state machines can not even parse context-free (Chomsky type-2) languages, so it definitely can not represent a general purpose program written in Word, even with a finite amount of memory.
Finite state machines can do anything that requires a finite amount of memory. For example, finite state machines can't recognize balanced parentheses. But they can recognize balanced parentheses in strings of length up to 10. There are only 2047 strings of parentheses of length up to 10, so you can have a state for each one and mark the valid ones as accepting states.
If we model the state of your computer, including every bit in ram, storage, caches, etc., then we know which state your computer will be in after the next clock cycle. We can therefore model your computer as a finite state machine, where each state represents the state of your computer at a given moment, and the transition is the result of your computer operating for a clock cycle.
There are a finite amount of possible states, and the transitions are deterministic. This defines a finite state machine.
You can't define a finite-state machine that can do everything that Word can do in principle, but you can define one that can do everything that Word can do on your computer, or in a VM. There would be way more states in this machine than there are atoms in the universe, but it's within the power of this theoretical construct.
Yes. I agree.
> Finite state machines can do anything that requires a finite amount of memory. For example, finite state machines can't recognize balanced parentheses. But they can recognize balanced parentheses in strings of length up to 10.
I already typed something similar before I changed my comment. I basically wanted to argue that it's theoretically correct, but we even dismiss it in computation theory, because modeling every state of a turing machine with just a few kilobyte of input is physically impossible.
But I was so unsure if that was actually true or there was a more fundamental problem that I convinced myself the "finite input" isn't the only thing that limits the capabilities of finite-state automatons vs pushdown automatons vs turing machines. I'm still not entirely sure, but I was thinking exactly the same as you explained.
A turing machine is simplified a finite state automata with random access memory and you can use that memory to setup communication. Yes the communication isn't part of the turing machine anymore, but our computer programs dictate what to communicate and we know what to send to create a certain output. That's what I meant with ingenuity to create these programs.
There is no real difference between any turing complete programming language or program apart from the libraries that help us do what we want.
That Word uses a GUI and sed uses a terminal/console is no difference at all in that regard. Both are a graphical user interface. It's just that Word dictates exactly what it wants to display, while sed just sends text and lets the console dictate how to display that text. Both is using a turing machine to create the data that finally creates an image on our display.
Nor do processors these days. To the cpu, keyboards, networks, and displays are just electronic signals and the cpu drives a logic to interpret and control those signals. The logic could as well be driven by a program running on a Turing machine, albeit awkwardly of course.
You could also argue that a Unix tool that reads stdin and writes to stdout doesn't have displays or keyboards, and is limited in what it can do. Yet the input/output streams are an abstraction: if we hook the output stream to drive a display and connect the input stream to keyboard event generator the program can certainly drive a graphical interface even if particular Unix tool itself has absolutely no notion of a keyboard nor a display. It just sees bytes in, bytes out, as programmed.
They have an infinite tape and compute (partial) functions from input words to output words, written on that tape. There are many things you can do that a TM can't do. Interactive computing is one of them.
Turing machine is a theoretical model of a computing machine as far it goes to reality itself, but the model does involve the bare essentials to do meaningful work such as input and output. And it is that input and output are what would allow it to be hooked into something that is real.
Given the realism of that we don't actually have infinite tapes either, any hypothetical application of a Turing machine would obviously manipulate the tape to give the program initial input and interpret the tape to read output in order to have the program do useful work.
The notation of an infinite tape is just Turing machine's only way to handle input and output, but it is really an abstraction for any input and output.
The Turing machine doesn't care where the data on the tape came from or if the output is interpreted as letters, pixels, or audio.
For inputs one could introduce memory-mapped peripheral registers, like the M68K does.
The original definition of TM can be preserved if you consider that you are introducing the notion of an outside world that would look at the tape at the end of the TM run (for display etc.) and feed another tape with different initial cell states (peripheral register values) for the next run.
> simulation is not reality.
Virtual machines and emulators are however quite useful ; and it seems that for some people, simulating human intelligence is the Graal.
I've tried it. I could get it to apparently "work". But then I'd get some input that hosed it. Now I just use "w3m -dump". I mean, it's a browser.
[0]: https://stackoverflow.com/questions/1732348/regex-match-open...
from 7 years ago: https://news.ycombinator.com/item?id=3855616
echo loop | sed -e ':x' -e 'p ; bx'The halting problem is an abstract theoretical result that I’ve personally never been concerned about, in any language at all. Not even once in practice in 30 years of coding have I worried that I didn’t know whether a correct bug-free program would finish. I worry that programs take too long all the time, but that’s completely separate from the halting problem.
If sed is a “bad thing”, just understand that string replacement is a “bad thing” and computers are a “bad thing”. There isn’t an alternative to doing any real computation without having Turing completeness.
One of my non-Turing complete languages is Animstack [1]. It's a script within GIMP image editing software. Imagine accidentally creating an infinite loop while you're working on an image and having your image editor freeze forever. Well, you can't create an infinite loop in Animstack. It's guaranteed to finish in linear time (of the number of layers). That's intentional and I was careful to preserve this guarantee.
The academic idea of the halting problem is not to make good UI or save people from themselves or from bugs, it’s just a theoretical math problem, and it doesn’t mean anything useful in practice.
You can write an infinite loop in C, and still hit Ctrl-C to kill it. You can screw up JavaScript and still close the tab. Turing completeness is not a problem in practice. If GIMP’s scripting or plugin environment doesn’t support killing a runaway script, then the bad UI is GIMP, not Turing completeness.
Plus, lack of Turing completeness is no guarantee that a script will be fast and that it won’t be bad UI. The halting guarantee is not a user guarantee on responsiveness or on run time at all.
Lack of Turing completeness might, on the other hand, severely limit real functionality, it might keep users of your language from being able to do cool things. You’re taking at least some kinds of higher level function composition off the table.
Anyway, that said, I will try to check out your project, I’m a big fan of image generation DSLs (having written a couple myself for CG film production) as well as compositing and animation projects.
To use your Animstack project as an example, you're not allowing your users to write things like Perlin turbulence (multiple octaves of noise) without a loop, or custom convolutions, or a Mandelbrot fractal, or 2d fluid flow. There are all kinds of practical and fun things you're artificially restricting yourself from. Some of those things can be technically done without TC, but none typically are because it's inconvenient, and because TC doesn't cause any practical problems.
Other examples that use Turing completeness in practice: UI event loops (all videogames, all of robotics, all servers of any kind), string replacement, sorting a list of arbitrary size, searching a list of arbitrary size, path tracing renderers, file i/o, regression and any non-linear optimization, I could go on for a very long time, the list is really long.
I'd like to know what interesting things you think you can do without conditional loops in a convenient way. Not what's theoretically possible if you bend over backwards, but what's practical and easy. I feel like the list is pretty short.
You also didn't answer the question. What is a real problem with TC? Killing runaway programs & infinite loops is not a problem in practice, and therefore neither is preventing people from writing infinite loops. So what's a problem with TC that I should care about? You can never guarantee people won't make mistakes, unless you make all their decisions for them. That's what non-TC languages normally feel like; a recipe book for pre-decided outcomes, not very powerful, not very interesting.
Nor did you address the fact that a decidable non-TC language doesn't guarantee halting in any reasonable amount of time. So how is it actually helping you to prevent TC? It doesn't seem like it is.
Here's a question- how many conditional loops did you use in the implementation of Animstack, under the hood?
A lot of these don't require Turing completeness. Anything that can be given runtime guarantee that's O(n^k) or even O(e^n) can be implemented without Turing completeness. Now if you need O(Ackerman-function) runtime, you gotta bring out the Turing machine, but I don't think such algorithms exist in practice.
Consider that pure SQL is not Turing complete. You can "search lists of arbitrary size" in it. And you can construct pretty complex queries in it to do so. It's the most popular programming language around and most people don't use the parts that make it Turing complete.
>Almost everything interesting in the computing world is done using conditional loops.
There's almost nothing that requires conditional loops with arbitrary conditions. Loops in Python all have the form "for element in sequence" and you can go pretty far without using custom iterators that allow for infinite sequences, which is considered an advanced topic. A lot of people program in non-Turing complete subset of Python!
> how many conditional loops did you use in the implementation of Animstack, under the hood?
I actually can answer this easily. It's implemented in TinyScheme (the scripting language of GIMP) which doesn't have loops, only recursion. So technically zero. Scheme is Turing-complete of course, but I don't think it has to be to implement Animstack.
There’s a lot of ignoring practice in your response. Python, C, O(n^k) algorithms, all of it is implemented with Turing Complete languages, whether it’s technically required or not. I don’t know the non-TC subset of Python you’re talking about, nor how many people are using it. Are they using it specifically to limit themselves to less powerful constructs, or for other reasons?
The web says SQL is in fact TC contrary to your claim. https://stackoverflow.com/questions/900055/is-sql-or-even-ts...
> There's almost nothing that requires conditional loops with arbitrary conditions.
The entire stack of tech you are using to type that sentence and send it over to Hacker news runs on intentionally infinite loops. The input element, the js in your browser, the event loop in your browser, your NIC and WiFi box, all the routers between you and HN, the web server responding to news.ycombinator.com. GIMP has an infinite loop waiting for user commands to launch your Animstack scripts.
My professional field is graphics, which is why I mentioned path tracing, and path tracing requires loops with arbitrary conditions, as do many statistical simulations. How would you write a non-TC memory manager? I don’t really know what you have in mind when you say almost nothing requires conditional loops, but I don’t see a lot of evidence of that being true. All video games run on while(1) loops.
You still didn’t answer my questions, so maybe this is as far as we need to go. Why does TC matter at all when you can kill a script? What is preventing TC buying your language when the programs are bug free? What is non-TC buying you when non-TC programs can take aribtrary amounts of time? Why is restricting the power of a language desirable? I havent seen a single reason yet that I buy.
Did you even read the link? You need extensions to make SQL Turing complete. Your replies indicate to me you lack the necessary theoretical background to discuss Turing completeness, since pure SQL not being TC is such a basic fact you don't need to look it up on the web.
The fact that the entire tech stack is TC is not a proof that TC is needed for individual parts of the tech stack. Indeed, some of the components of the web stack, namely CSS, are not TC (no, please don't look it up on the web and come back with "CSS is turing complete" bullshit, they're clearly wrong because halting problem of CSS is decidable).
By the way Turing machine doesn't involve human interaction, so all your examples that involve interactivity (UI loops) are outside of scope of this discussion.
>What is preventing TC buying your language when the programs are bug free?
There's no such thing as bug free program. When you need to execute arbitrary programs, not being TC buys you a lot of guarantees that can be useful.
Please, elaborate! What are these useful guarantees? Can you name some?
> Did you even read the link?
I think so... the first sentence says you don’t need an extension. The linked Mandelbrot set example is “SQL:2008 conformant” and depends on “nothing”. https://wiki.postgresql.org/wiki/Mandelbrot_set Is that using an extension?
> By the way Turing machine doesn’t involve human interaction, so all your examples that involve interactivity (UI loops) are outside of scope of this discussion.
Okay, so Turing completeness doesn’t apply to GIMP or Animstack at all, right? That’s what I was trying to suggest before. ;) Your own stated reason for removing TC from Animstack was UI.
Who says human input doesn’t apply? Alan Turing didn’t say that. Wikipedia says that interaction does apply: https://en.m.wikipedia.org/wiki/Turing_machine#Interaction “In principle, it is possible to model this [interaction] by having an external agent read from the tape and write to it at the same time as a Turing machine...”
> The fact that the entire stack is TC is not a proof that TC is needed
No, it’s just proof that TC languages are common and useful, and that not many practitioners would agree that TC is a “bad thing”.
> Indeed, some of the components of the web stack, namely CSS, are not TC
So? What does it prove if a few parts are non TC, when so many of them are?
CSS is for styling, not for writing programs, unlike Animstack and sed and the other examples you’ve been using. It tends to undermine your points a little bit to hold up CSS as an example of a non-TC language. I wouldn’t want to use CSS to compute things, so I don’t care if it’s Turing complete or not. For that matter, I don’t care whether any language is Turing complete, as long as I can get my work done easily, why should I?
> no, please don’t look it up on the web
Okay, I won’t. Just kidding, here’s the answer, not just a claim, but an implementation of Turing Completeness. So what’s clearly wrong about it? https://stackoverflow.com/a/5239256
To be honest, I don’t care what’s wrong with it. Or with sed or any other language. Not in purist academic theory. I wanted to hear if there are practical reasons to care, but since you won’t answer and I haven’t heard any, then I don’t care.
while(1) hang
# and
for(i < 9^9999) hangAsking for a friend
why is this glorified
Why is it glorified? Unless all these researchers are really just intentionally giving code word to hackers for a target to exploit or weaponize, but it doesn't really seem like thats the point with these people.
[1] https://en.wikipedia.org/wiki/Primitive_recursive_function
Since the Ackermann function is obviously computable, and easily computable by a Turing machine, this implies that the primitive recursive functions are not Turing complete, and thus more limited than the µ-recursive functions.
The term is confusing if you are used to “recursion” in the context of programming. Primitive recursion basically corresponds to programs that don’t use recursion or unbounded loops. For example “compute the factorial of 55” or “sort this input list of at most 10000 integers”.