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

61–70 of 91 posts

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

#61

Post by 0xTJ »

harpiaharpyja wrote: post #53

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…

As it's structured, that wouldn't work. To move, it replaces the leading zero of the tape with:

  * If the movement is "0": "00"
  * If the movement is "1": ""
The choice of 1 to move right is arbitrary (but makes sense to match the 0), it could be any other symbol, but the 0 is needed to because that's what's prepended to the tape.

Someone could probably find a way around it, but it would likely make it harder to understand.

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

#62

Post by aasasd »

metalliqaz wrote: post #30
kadoban wrote: post #26

Earlier quoted context omitted.

Learn basic syntax and you'll spend the next few decades wondering each time _which_ basic syntax is expected because none of them ever say.

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.

Quick: which programs use ‘|’ and which use ‘\|’?

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

#63

Post by skykooler »

tartoran wrote: post #27
dspillett wrote: post #12

Earlier quoted context omitted.

I find myself wondering if anyone has done a proper analysis to prove that human activity is Turing complete!

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

Given that Turing machines cannot be guaranteed to halt (and it's trivial to write an infinitely-running Turing machine), therefore humans are not, technically, Turing-complete.

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

#64

Post by Semaphor »

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…

> Some by "regex" mean "globs" and you can just use "*" and "?" for stand-ins for some number of characters.

What kind of scary tool is that?

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

#65

Post by hexane360 »

_jal wrote: post #51
kadoban wrote: post #34

Earlier quoted context omitted.

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.

*almost always: https://blog.cloudflare.com/details-of-the-cloudflare-outage...

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

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

#66

Post by RHSeeger »

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…

> Some by "regex" mean "globs" and you can just use "*" and "?" for stand-ins for some number of characters.

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.

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

#67

Post by RHSeeger »

Semaphor wrote: post #64
kadoban wrote: post #34

Earlier quoted context omitted.

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…

> Some by "regex" mean "globs" and you can just use "*" and "?" for stand-ins for some number of characters. What kind of scary tool is that?

Glob is used in most shells, plus in several languages (Tcl has both glob and regexp matching).

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

#68

Post by Semaphor »

RHSeeger wrote: post #67
Semaphor wrote: post #64

Earlier quoted context omitted.

> Some by "regex" mean "globs" and you can just use "*" and "?" for stand-ins for some number of characters. What kind of scary tool is that?

Glob is used in most shells, plus in several languages (Tcl has both glob and regexp matching).

Yeah, but they don't call it "regex" which would be the scary part.

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

#69

Post by chhickman »

skykooler wrote: post #63
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

Given that Turing machines cannot be guaranteed to halt (and it's trivial to write an infinitely-running Turing machine), therefore humans are not, technically, Turing-complete.

Well, I would say that any physical implementation of a Turing machine will eventually halt because you cannot guarantee an infinite energy supply. So if we're willing to ignore physical limitations then humans can be Turing complete - if not, then no machine be either.

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

#70

Post by teawrecks »

fouronnes3 wrote: post #6

Nice one to add to the list of accidentally Turing complete systems. What's your favourite :)?

I wouldn't say that it's on accident. The theoretical definition of Regular Expressions is specifically not Turing complete. But Regex as a tool just isn't as useful in that form, so it was deliberately extended to be Turing complete with new operators.
Post reply on HN