A functioning Turing Machine using Notepad++ and its find/replace regex engine
1–10 of 91 posts
Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine
#2I was under the impression that RegEx was not turing complete. Is there something special about N++’s regex engine that allows this?
Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine
#3I was under the impression that RegEx was not turing complete. Is there something special about N++’s regex engine that allows this?
No, nothing special about N++ (well, lookahead, but many regex engines have that). Repeated Search+Replace is the key, and not part of regex.
Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine
#4I was under the impression that RegEx was not turing complete. Is there something special about N++’s regex engine that allows this?
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
Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine
#5I was under the impression that RegEx was not turing complete. Is there something special about N++’s regex engine that allows this?
[deleted]
Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine
#6Nice one to add to the list of accidentally Turing complete systems. What's your favourite :)?
Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine
#7Cool 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 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.
Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine
#8Nice one to add to the list of accidentally Turing complete systems. What's your favourite :)?
Still one of my favorites: On The Turing Completeness of PowerPoint, https://www.youtube.com/watch?v=uNjxe8ShM-8
Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine
#9Not a Turing machine if the user has to press a button for each step.
Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine
#10Not 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..