Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A functioning Turing Machine using Notepad++ and its find/replace regex engine

github.com

Post reply on HN
Print view View original

51–60 of 91 posts

Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine

#51

Post by _jal »

kadoban wrote: post #34
metalliqaz wrote: post #30

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

Some by "regex" mean "globs" and you can just use "*" and "?" for stand-ins for some number of characters. 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 tha…

Look for 'pcre' on the label. Accept no substitutes and you'll be fine.

Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine

#52

Post by [deleted] »

nsajko wrote: post #43
louhike wrote: post #36

Earlier quoted context omitted.

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

[deleted]

Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine

#53

Post by harpiaharpyja » 

   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.
Would it have been clearer to use "" to specify whether to move left/right from the current position?

Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine

#55

Post by Banana699 »

vermilingua wrote: post #2

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

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.

Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine

#56

Post by Banana699 »

coldtea wrote: post #10
kats wrote: post #9

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

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

Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine

#57

Post by Banana699 »

KptMarchewa wrote: post #25
kats wrote: post #9

Not a Turing machine if the user has to press a button for each step.

Not a Turing machine if it's powered by human created electricity.

Terrible and fallacious analogy, the repeated press of a button doesn't power the search+replace process, it still needs electricity to run, the repeated pressing is more like a hardware clock that repeatedly pulses to advance the computation, which does indeed makes the search+replace process alone not turing complete, every turing machine has control logic to automate the execution loop.

Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine

#58

Post by tartoran »

thehappypm wrote: post #39
tartoran wrote: post #27

Earlier quoted context omitted.

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.

Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine

#59

Post by notahacker »

Banana699 wrote: post #55
vermilingua wrote: post #2

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

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…

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

Re: A functioning Turing Machine using Notepad++ and its find/replace regex engine

#60

Post by aasasd »

midjji wrote: post #13

Neat, 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…

If anyone whose life line says ‘makes an editor’ is reading the above: I beg you to use Lua instead of Python. It's a lot faster, and that matters in productivity apps. Speed can be the difference between ‘I wrote a script’ and ‘I could write a script but didn't’.
Post reply on HN