Earlier quoted context omitted.
Certainly; that's a space bounded computation, only needing O(n) tape for n disks.
But will it run Doom?
Nowadays we ask "will it run LibreOffice?"
A functioning Turing Machine using Notepad++ and its find/replace regex engine
81–90 of 91 posts
Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine
#82Earlier quoted context omitted.
You must not have suffered enough, I mean used regexs widely enough. 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: https://swtch.com/~rsc/regexp/regexp1.html
I just don't count those cases as 'basic' syntax.
Basic - naming a capture group.
Awk / posix - \1
Perl - $1.
Python - (?P).
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.
Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine
#83Earlier quoted context omitted.
That'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..
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. >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 mac…
No, Babbage's earlier design requires the crank to be turned all the time. Basically human-powered instead of fossil-fuel powered. As long as the human only needs to turn the crank without thinking, the human could always be replaced by a steam engine.
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.
Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine
#84Earlier quoted context omitted.
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. >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 mac…
> 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…
>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.
Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine
#85Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine
#86Cool 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…
Yep! 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.
Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine
#87Not a Turing machine if the user has to press a button for each step.
That'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..
It's pretty relevant. A simple arithmetic equation becomes Turing complete if a helper system is attached to execute it over and over on the previous output.
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.
Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine
#88Earlier quoted context omitted.
I 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.
You must not have suffered enough, I mean used regexs widely enough. 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: https://swtch.com/~rsc/regexp/regexp1.html
Oh and dont forget that just because the documentation says it uses a specific regex syntax, that does not mean its correctly implemented. It gets worse when an application examples specify a specific syntax but what happens in the background is that it will use the default reg exp engine, which can be system or enviroment specified.
Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine
#89Neat, 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 i…
I wouldn't be happy with Python, but I do agree with the general premise that extensibility or automation ought to be expected of editors. 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 m…
Yeah it does not need to be python, I dropped emacs lisp due to (pain), never liked bash, or perl. Java like in matlab isnt nice either, too damned verbose. Ruby might work, most webstuff is great at showing stuff, but I havent tried it.
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!
Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine
#90So what you're saying is I could use this to parse HTML?
Who said that regexes could not be used to properly parse HTML? ;-)