A functioning Turing Machine using Notepad++ and its find/replace regex engine
github.com
github.com
> 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.
The 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.
* If the movement is "0": "00"
* If the movement is "1": ""
Someone could probably find a way around it, but it would likely make it harder to understand.
When combined with enhanced regexes (backreferences and lookahead), you have the ingredients for Turing completeness.
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.
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..
>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.
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".
Yes, that's exactly what I'm saying. And that's why the title is misleading, it's not really Notepad++'s search and replace feature that is turing complete on it's own, because turing complete means "can *Simulate* an arbitary turing machine", the 'can' here is not meant to imply a "if you sat next to it and repatedly pressed enter" kind of remark, it just means you can vary the machine being simulated by varying the input string, but once you enter an input string into the turing-complete system, it should be able to simulate the machine on it's own while you step back and watch. That's what the original machine would have done anyway, so how can you 'simulate' a turing machine if you need something it doesn't ?.
Leave Notepad++'s search and replace feature on a text file containing a transition table for 10^9 years, would it simulate anything on it's own ? On the other hand, leave a JVM running for 10^9 years... you get what I mean.
This is mostly an informal philosophical disagreement on the actual vs. the potential, real academic proofs of turing equivalence side-step the matter of simulation entirely by describing the systems involved in static terms. It's implicitly assumed there is a background animator stepping every system according to its rules.
But I think it's relevant to our intuitive definition of what a computer is, I don't think anyone ships their programs in a form where the user needs to invoke a debugger and repeatedly press 'step over' to get to the next state of the computation. Those kinds of "X is turing complete" headlines circulate on social media and leads people to think 'X' can actually act as an automatic computer, but little do they know the author uses their hand as a hardware clock without really calling attention to it.
The purpose of Turing completeness is to describe whether a system is capable of performing arbitrary computation. That once a machine is Turing-complete, Church-Turing thesis stipulates it can do any computation that another Turing-complete machine can do, subject to resource and time constraints.
In the early days of computing, where designing and building a general-purpose computer was still a major practical challenge, one could imagine whether the crank is turned by a human wasn't important, because any idea that involves a physical crank can be supplemented by a steam engine, a solved problem. It's very easy to swap out the human for a steam engine - the actual novel problem was to verify that the internal logic of the machine is general-purpose enough.
In that context, one can see what the true spirit of the Church-Turing thesis is. It abstracts away the things that don't need to be part of the picture, so that people can focus on understanding the mathematical notion of computation - what is computable and what isn't, and what kind of designs are capable of computing everything that's computable.
To illustrate, you'd say it's imprecise to say a language is Turing complete - you technically still need a CPU and RAM. But those are just assumed to be available when the true focus is to design a language. Similarly, when designing a mechanical computation machine, whether we have built in the monotonic power source / hardware clock is just not a very important distinction given the context of the design. Everything that holds for Turing-complete machine would still hold, just except the machine needs a power source.
It's true that requiring constant clicks makes the result less interesting (and maybe very much so), but for the spirit of Turing completeness the power source is just a trivial matter.
The class of things that are Turing complete with one button push is much smaller than the class of things that can run a single step of a Turing machine per button push.
I'm not here to argue about which one is the "real" Turing complete, but they're very distinct groups, and I'd say that getting into the former is significantly more impressive and interesting than the latter.
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.
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.
>The Lua WAF uses PCRE internally and it uses backtracking for matching and has no mechanism to protect against a runaway expression.
https://blog.cloudflare.com/making-the-waf-40-faster/
>Back in July 2019, the WAF transitioned from using a regular expression engine based on PCRE to one inspired by RE2, which is based around using a deterministic finite automaton (DFA) instead of backtracking algorithms. This change came as a result of an outage where an update added a regular expression which backtracked enormously on certain HTTP requests, resulting in exponential execution time.
>After the migration was finished, we saw no measurable difference in CPU consumption at the edge, but noticed execution time outliers in the 95th and 99th percentiles decreased, something we expected given RE2's guarantees of a linear time execution with the size of the input.
What kind of scary tool is that?
> Some [people] by "regex" mean "globs"
But that's _not_ regexp, it's glob; a totally different pattern matching system. I mean, you can call a duck a horse, but that doesn't mean you're right... or that there's anything confusing about horses.
He meant “syntax” in the sense that different regex engines have different syntax and capabilities - can I do a negative look ahead assertion in engines Z, how do I do a zero width lookaround in pcre, gnu, python, posix, etc.
Depending how far down the rabbit hole you want to go, start here:
I’d find it hard to ignore the specifics. I mean if you only ever use one tool and were never exposed to other regex engines I guess.
My own editor is written in Ruby, and so all extension is done by loading Ruby code into the running process, and I can drop into the Pry debugger with a keypress, or another keypress gives me a prompt to enter a single-line expression instead. The latter is literally a one-line method. Adding a binding to eval() a whole buffer would be equally trivial... Being able to extend everything trivially in a language I'm comfortable with (so not Emacs lisp) makes such a difference to usability.
Incidentally, the ability to interact with the open buffers using a script also from outside the editor is another thing I love as an extension mechanism for editors - an idea I first saw in FrexxEd (co-written by the founder of Curl) for the Amiga, which exposed the open buffers in the filesystem (think the Amiga equivalent of a FUSE filesystem), which would have the added benefit of not being language specific. It doesn't need to involve any FUSE-like stuff either - just a command line utility to "cat" an open buffer and to replace the open buffer from stdin would be sufficient.
E.g. I have functions in there to insert headers in my journal for example.
In terms of executing code "actually" live, it's ~80% for debugging when I work on the editor itself. Pry provides all of the plumbing so all the code needed to add that is just to suspend the editors own input handling and call pry, coupled with an exception handler that calls pry as well, so there was no reason not to, basically.
But once I'd added it, the 20% left felt worthwhile as a means of e.g. do complex searches, or generate tables or otherwise do search and replace of content that requires more (e.g. parsing timestamps and replacing them with another format....) and any number of things I don't do very often but that feels very comfortable when you do need it. To be clear it's not like it does much you can't do easily without it. E.g. after all I could just dump the buffer to a file, load it in my repl of choice, manipulate it and write it out again and reload it in my editor. It's one of those small things that feels unimportant when you don't have it there, that doesn't save you a huge amount of time, but that just makes things feel nicer when you get used to them.
The generic variant would be to make it modular and replaceable, but that would be a mistake, I would much rather have a tool good at a specific subset of jobs than a config heavy tool which is medicore at all. Perhaps advanced search and replace fits that, but I think its a fundamental aspect of editing.
Thats a good idea!
Before that i used to write scripts or even full programs (in Free Pascal which has some simple string handling) to do similar processing and i did find it much more cumbersome to go through that route.
Of course this only works for editing/generated/transforming text pieces (and i pretty much always use it via clipboard), for processing files i still end up writing full scripts or programs (depending on the case, if i need to preprocess stuff i use another LIL-based tool, lip[4]).
[0] http://runtimeterror.com/tools/liteproc/
[1] http://runtimeterror.com/tech/lil/
[2] http://runtimeterror.com/tools/liteproc/shot.png
Never got around to making it properly interactive, because I stopped needing it when I switched to Emacs and had both its native capabilities and C-u M-| available.