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