Hacker News Reader

Comment by vermilingua | Hacker News Reader

I was under the impression that RegEx was not turing complete. Is there something special about N++’s regex engine that allows this?

View on HN

Regular 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.

Seems 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!)

No, nothing special about N++ (well, lookahead, but many regex engines have that). Repeated Search+Replace is the key, and not part of regex.

Aaah of course, thanks

I find myself wondering if anyone has done a proper analysis to prove that human activity is Turing complete!

We can manually execute the steps of a Turing machine. That's all that's needed.

It is so, trivially; humans wrote the find/replace box in Notepad++.

I mean, I can write a FSM that outputs the code for find/replace in Notepad++.

Yeah, but you can't write an FSM that can execute itself repeatedly over its own output indefinitely!

We 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

How about a human population?

Oh, 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.

Given 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.

Well, 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.

Turing 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.

Turing's original idea of a "computer" was a human manipulating symbols on paper, so I would say trivially yes

So, Notepad++ basic interface is Turing complete because it's a place you can write a Turing machine and execute it.

And 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

It 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.

Do you mean Chomsky hierarchy by Chomsky regex?

Regular languages are an element included in Chomsky's hierarchy: https://en.wikipedia.org/wiki/Chomsky_hierarchy https://en.wikipedia.org/wiki/Formal_language

It 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.

Reply on news.ycombinator.com