9 ms·
A functioning Turing Machine using Notepad++ and its find/replace regex engine
- vermilingua 5y agoI was under the impression that RegEx was not turing complete. Is there something special about N++’s regex engine that allows this?
- deleted 5y ago[deleted]
- detaro 5y agoNo, nothing special about N++ (well, lookahead, but many regex engines have that). Repeated Search+Replace is the key, and not part of regex.
- vermilingua 5y agoAaah of course, thanks
- dspillett 5y agoI find myself wondering if anyone has done a proper analysis to prove that human activity is Turing complete!
- vidarh 5y agoWe can manually execute the steps of a Turing machine. That's all that's needed.
- dTal 5y agoIt is so, trivially; humans wrote the find/replace box in Notepad++.
- teawrecks 5y agoI mean, I can write a FSM that outputs the code for find/replace in Notepad++.
- sudosysgen 5y agoYeah, but you can't write an FSM that can execute itself repeatedly over its own output indefinitely!
- tartoran 5y agoWe are guaranteed to halt, e.g lifespan. After death cells enter apoptosis stage where cells do final stages upon shutting down. I’d say it appears we are Turing complete, or at least it appears so from this angle
- thehappypm 5y agoHow about a human population?
- tartoran 5y agoOh, that too though we’re looking at it from a different angle. Most species so far have gone extinct though we’re a special kind, we may as well cause that without any external factors.
- skykooler 5y agoGiven that Turing machines cannot be guaranteed to halt (and it's trivial to write an infinitely-running Turing machine), therefore humans are not, technically, Turing-complete.
- chhickman 5y agoWell, I would say that any physical implementation of a Turing machine will eventually halt because you cannot guarantee an infinite energy supply. So if we're willing to ignore physical limitations then humans can be Turing complete - if not, then no machine be either.
- walnutclosefarm 5y agoTuring completeness is a theoretical construct that ignores that errors in execution inevitably occur during a sufficiently long program, due to the second law of thermodynamics (entropy must increase in a closed system). Any realization of a Turing complete engine eventually fails. That's different than halting, though, because it doesn't answer the question as to whether the program of the machine eventually reaches a halt instruction, when properly executed.
- assbuttbuttass 5y agoTuring's original idea of a "computer" was a human manipulating symbols on paper, so I would say trivially yes
- lupire 5y agoSo, Notepad++ basic interface is Turing complete because it's a place you can write a Turing machine and execute it.
- lifthrasiir 5y agoAnd if you allow multiple pattern-replacement pairs, you don't even need regex (the pattern can be a single fixed string) as it is enough to simulate semi-Thue systems [1]. [1] https://en.wikipedia.org/wiki/Semi-Thue_system https://en.wikipedia.org/wiki/Semi-Thue_system
- ptspts 5y agoIt is proven that Turing machines can recognize a wider class of languages than Chomsky regular expressions. However, the article uses something more powerful than Chomsky regular expressions, because they contain backreferences (as \2 and \4), and also there is a repeated search-and-replace involved, which also adds to their power.
- louhike 5y agoDo you mean Chomsky hierarchy by Chomsky regex?
- nsajko 5y agoRegular languages are an element included in Chomsky's hierarchy: https://en.wikipedia.org/wiki/Chomsky_hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy https://en.wikipedia.org/wiki/Formal_language https://en.wikipedia.org/wiki/Formal_language
- deleted 5y ago[deleted]
- baryphonic 5y agoIt seems Notepad++'s "search + replace all" feature replaces text in place inside a search context rather than buffering the changes and applying them outside a search context after the search is complete. This makes search recursive. When combined with enhanced regexes (backreferences and lookahead), you have the ingredients for Turing completeness.
- Banana699 5y agoRegular Expressions as defined mathematically is strictly less powerful than turing machines. (by several levels, they are strictly less powerful than general context-free grammars, which are strictly less powerful than general context-sensitive grammars, which are strictly less powerful than arbitary grammars) The 'regexes' in modern languages and tools, however, are not actually regular in the original mathematical sense, they have been augmented by several constructs that are not regular. Perl is the leader in this field, its latest addition is regexes which can reference itself recursively, making (presumably, never seen a proof) it at least context-free. Here, the non-regular constructs used is capture groups and arbitary forward lookahead. In addition to that, the author is doing something sneaky by making the user press a button continuesly to advance the state of the turing machine, so it's not actually search+replace that is turing complete, it's search+replace+"repeatedly pressing replace all". Unlike what some other people say in this thread, repeatedly pressing a button to simulate the machine doesn't count as 'turing complete' and is not comparable to plugging the machine in power.
- notahacker 5y agoSeems like you could use automated hardware to repeatedly press the button to facilitate the computation without any additional software or human interaction required (I'm reminded of the episode of the Simpsons where Homer tries to automate his job with a nodding bird!)
- fouronnes3 5y agoNice one to add to the list of accidentally Turing complete systems. What's your favourite :)?
- giu 5y agoStill one of my favorites: On The Turing Completeness of PowerPoint, https://www.youtube.com/watch?v=uNjxe8ShM-8 https://www.youtube.com/watch?v=uNjxe8ShM-8
- teawrecks 5y agoI wouldn't say that it's on accident. The theoretical definition of Regular Expressions is specifically not Turing complete. But Regex as a tool just isn't as useful in that form, so it was deliberately extended to be Turing complete with new operators.
- Pompidou 5y agoA bit off topic but in the french internet there is an add, these days, asking people to try the Turing test to find a (good) job. I find it very funny. Imagine a job interview where you have to be turing-complient to get the job : you play the tape and the recruiter act like a scanning device...
- tromp 5y agoCool demonstration of regular expression power! Note that as implemented, this is a space bounded Turing Machine with a hardcoded tape length limit: > With the current implementation, the read/write head looks at the 22nd element of the tape whenever we want to read the current position. With complicated machines that utilize long lengths of the tape, you would need to increase this number so that you never delete a necessary tape element as you scroll along it. This can be done by increasing the {20} that appears at the beginning of the expression. Embedding the tape head pointer ^ within the tape, just to the left of the scanned bit, should remove this restriction.
- brownieinmotion 5y agoYep! Embedding the tape head and the current state on the tape would make this more than just PSPACE-complete. I believe that in this case, regular expressions would not even be necessary: the Turing machine could be simulated with JUST find and replace.
- kats 5y agoNot a Turing machine if the user has to press a button for each step.
- coldtea 5y agoThat's not relevant as to whether it's a turing machine or not, tho... The possible calculations (and genericity) is what matters. The "button for each step" could be analogous to powering the turing machine, or turning some crank for Babbage's machine, or whatever..
- floatboth 5y ago…or clicking the On-Click Transitions in Microsoft® PowerPoint™…
- Banana699 5y agoThis is absolutely relevant, turing's original definition described a completely autonomous and automatic machine, that's why every turing machine has a halting state that locks it in a loop when computation is finished. >could be analogous to powering the turing machine, or turning some crank for Babbage's Those things are done once for those machines, you press power-on or turn a crank for just one time and the machine starts, this is not the case here, here the human is acting as the control logic for the machine, repeatedly pulsing to drive the computation. Your computer is not a computer without a hardware clock, the repeated pressing of a button is acting as a hardware clock here.
- coldtea 5y ago>This is absolutely relevant, turing's original definition described a completely autonomous and automatic machine, that's why every turing machine has a halting state that locks it in a loop when computation is finished. That's just an accidental part, and is orthogonal to the manual "click next". The halting state absolutely will be there, locked in a loop and everything, you just manually click to step over each iteration of that loop. As said, the "click next" is no different that a clock signal in a CPU, or manually cranking the turing machine to play. It's not at all relevant to the abstraction. >Your computer is not a computer without a hardware clock, the repeated pressing of a button is acting as a hardware clock here. Which is exactly why it's an irrelevant detail to the turing machine computation. It's just the clock, not the digital logic. Whether the hardware clock is internal, or external, or I have a mule rotate around a millstone to drive it, or a big chunk of quartz, is irrelevant, as long the machine is receiving it. This includes me clicking a button to send a pulse. Let's put it another way, what you're saying is isomorphic to: "This setup is not a turing machine but this exact setup plus a while loop to repeatedly call xsendkey for Enter is".
- numeri 5y agoI did essentially this in vim once – although I made it a little more "user friendly" with vim macros' ability to both call and modify themselves, so it would stop itself if the Turing Machine halted.
- midjji 5y agoNeat, Though it does make me wonder if a python parser wont soon become standard in editors. Its just too damned convenient for many things, sure you might be able to come up with a regexp search and replace that does the same thing, but odds are it will take longer than coding a few loops. BASH sucked far too much, and C++ and most languages lacked the convenient filesystem libs required, but python just works and is easy to read and modify. The downsides of python, like the atrocious speed and low maintainability dont matter for scripts you will use just once.
- tjoff 5y agoPython just works... Every now and then I'm still bitten by the 2->3 transition. And I'd very much not like it to be a required dependency in my systems either. And no, regexps get a bad rep but they are for the easy 99% and insanely quick to come up with. Learn basic syntax and you'll be thankful for decades to come.
- kadoban 5y agoLearn basic syntax and you'll spend the next few decades wondering each time _which_ basic syntax is expected because none of them ever say.
- metalliqaz 5y agoI know the basic syntax and I never have that problem. Perhaps you mean the advanced syntax? However I don't see the problem, there either. I usually don't need it, and to be honest, when I do, I find it more maintainable to use multiple simpler expressions combined with some programming.
- kadoban 5y agoSome by "regex" mean "globs" and you can just use "*" and "?" for stand-ins for some number of characters. Some allow "|", some allow backrefs, some allow "()", or require them escaped with \, or allow them but not with * after. Some are case insensitive, some not. Some allow "{0-5}", some allow "[0-9]", some have handy things like "\w". It's just the guessing game of exactly what they want. It should be required that each regex box has an example next to it using as many allowed features as possible.
- dom111 5y agoIf you like this, you might also like Retina[0]! [0]: https://github.com/m-ender/retina/tree/master/Examples https://github.com/m-ender/retina/tree/master/Examples
- unixhero 5y agoSo it can play Towers Of Hanoi?
- tromp 5y agoCertainly; that's a space bounded computation, only needing O(n) tape for n disks.
- drexlspivey 5y agoBut will it run Doom?
- dboreham 5y agoNowadays we ask "will it run LibreOffice?"
- lupire 5y agoIf you like this, you'll love Save Endo, one of the top two most fun ICFP Programming Contests ever. (The other is Cult of the Bound Variable) https://save-endo.cs.uu.nl/ https://save-endo.cs.uu.nl/
- NextHendrix 5y agoSo what you're saying is I could use this to parse HTML?
- ktpsns 5y agoWho said that regexes could not be used to properly parse HTML? ;-)
- colejohnson66 5y agoParsing HTML can be done with a state machine. That’s how HTML5 defines how to parse it: https://html.spec.whatwg.org/multipage/syntax.html#syntax https://html.spec.whatwg.org/multipage/syntax.html#syntax
- DeathArrow 5y agoGreat, now someone should write a Javascript interpreter for it!
- wjd2030 5y ago"Yeah, but your scientists were so preoccupied with whether or not they could, they didn't stop to think if they should" - Dr. Ian Malcolm.
- wjd2030 5y agojokes, this is neat.
- harpiaharpyja 5y agoThe instruction sets are the remaining lines, formatted like >C.I:WMN C current instruction name. I the input from the current tape position. Either 0 or 1. Each instruction has execution parameters for both inputs. W the output to be written to the tape at the current position. Either 0 or 1. M the movement of the read/write head. A 0 moves the head one position to the left. A 1 moves it to the right. N the name of the next instruction to be executed at the new tape position. Would it have been clearer to use "<" or ">" to specify whether to move left/right from the current position?
- 0xTJ 5y agoAs it's structured, that wouldn't work. To move, it replaces the leading zero of the tape with: * If the movement is "0": "00" * If the movement is "1": "" The choice of 1 to move right is arbitrary (but makes sense to match the 0), it could be any other symbol, but the 0 is needed to because that's what's prepended to the tape. Someone could probably find a way around it, but it would likely make it harder to understand.
- armchairhacker 5y agoAh yes, regular expressions, my favorite Turing-complete language.
- JadeNB 5y agoI made a harder-to-understand investigation using Perl (non-regular, of course) regexps a while back. https://perlmonks.org/?node_id=809842 https://perlmonks.org/?node_id=809842