4 ms·
I was under the impression that RegEx was not turing complete. Is there something special about N++’s regex engine that allows this?
by vermilingua 5y ago
I 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!)