RegEx Turing Machine

MartinBraendli2

I played a bit around with Find/Replace and RegEx in Notepad++ and came up with this:

find:

(>─)|(─>┼)|(┼>┼)|(╫>┼)|(─>╫)|(┼>╫)|(╫>╫)|(─►─)|(┼►─)|(╫►─)|(►┼)|(►╫)|(^[>►])|([>►]$)

replace:

(?1┼►)(?2>─╫)(?3>┼╫)(?4>╫╫)(?5>─┼)(?6>┼┼)(?7>╫┼)(?8>─╫)(?9>┼╫)(?10>╫╫)(?11╫►)(?12─>)(?13─$13)(?14$14─)

This is an implementation of Wolfram's 2-state 3-symbol Turing machine. To use it, create a new file in an Editor that knows RegEx, like Notepad++. Enter nothing but a ‘>’ Symbold (Greater than, ASCII 62). Then use the 2 RegEx to find and replace. Click on “replace all” multiple times to see the Touring Machine working. Here is an example output. Each line is the content of the file after “replace all” clicked once.

>
─>
─>─
─┼►
─┼►─
─>┼╫
>─╫╫
┼►╫╫
┼─>╫

Symbols:

>	Turing Machine in State A (it alsways reads the char right to it)
►	Turing Machine in State B
─	Empty tape, 0
┼	1 on tape
╫	2 on tape

Try it, its really fun to watch. Of course you can also run this with a “tape” that is not empty at the beginning.

Last edited by MartinBraendli2 (Oct. 22, 2017 13:50:40)

ScratchMan544

What regex flavor is this?

_=(lambda _:lambda __:_(__))(lambda _:getattr(_,(
    lambda _:_[:2]+str(print.__call__)[0b10011:(1+1<<1+1+1)+(1<<1+1)+(1<<1)+1]+_[-2:]
)(__name__)))(eval)
(lambda _:lambda __:_(__))(lambda _:_(_(
    __import__(dir(__builtins__)[((1<<1+1)<<1+1+1)+(1+1<<1+1+1)+(1+1<<1)+(1<<1)][:3].lower()),
    print.__doc__[46:52]),open(__file__).write.__str__()[17:22]))(_("getattr"))((
    lambda _:lambda __:_(_,__))(lambda _,__:""if __==0else chr(__%128)+_(_,__//128))(963149002634454890336513358634316810781103160855182366005237514)[::-1]
)

NickyNouse

ScratchMan544 wrote:
What regex flavor is this?

Apparently very close to Perl regex: http://docs.notepad-plus-plus.org/index.php/Regular_Expressions

Update: none of the Perl regex testers I've found online have worked but I'm too lazy to download notepad++

Last edited by NickyNouse (Oct. 23, 2017 05:45:47)

MartinBraendli2

ScratchMan544 wrote:
What regex flavor is this?

I used the syntax of regexr.com:

While the core feature set of regular expressions is fairly consistent, different implementations (ex. Perl vs Java) may have different features or behaviours.
RegExr uses your browser's RegExp engine for matching, and its syntax highlighting and documentation reflect the JavaScript RegExp standard.

So I guess its the JS standart.
Hm, don't know what flavour it is, i just tried different stuff and if it worked in Notepad++ i kept it.

Last edited by MartinBraendli2 (Oct. 23, 2017 21:21:05)

NickyNouse

MartinBraendli2 wrote:
ScratchMan544 wrote:
What regex flavor is this?
I used the syntax of regexr.com:
While the core feature set of regular expressions is fairly consistent, different implementations (ex. Perl vs Java) may have different features or behaviours.
RegExr uses your browser's RegExp engine for matching, and its syntax highlighting and documentation reflect the JavaScript RegExp standard.
So I guess its the JS standart.

I'm not getting it to work there: http://regexr.com/3h186

OH I was using substitution not list – looks good lol
edit: it was working for like 1 second and now it's not

regexr is too complicated for me

Last edited by NickyNouse (Oct. 23, 2017 20:32:16)

walkcycle

is this anything like this?

Trump-Russia Timeline

Meditation with Biscuit | SOFAANISQATSI | Lost Satellite Found | Riddles in the sky

novice27b

This is great, and I'm actually surprised you're the first person to do this.

A quick googling returns results where people say that regex itself is not turing complete (which is true in most cases), but it doesn't look like anyone has tried a repeated find-and-replace before.

i use arch btw

MartinBraendli2

novice27b wrote:
This is great, and I'm actually surprised you're the first person to do this.

A quick googling returns results where people say that regex itself is not turing complete (which is true in most cases), but it doesn't look like anyone has tried a repeated find-and-replace before.

Yeah, I was surprised myself not to find any results on that matter. Maybe I'll implement Brainflakes in RegEx. It should be a bit easier than I thought, now that i know that you can nest capturing groups. However, it would still be quite a challange.

TheUltimatum

So what does it even do? I can see it moving around but what does state b do?

solve the cube

MartinBraendli2

TheUltimatum wrote:
So what does it even do?

EVERYTHING (computationally). Its a somewhat universal turing machine, so it can compute everthing that can be computed (given the right input on the “tape”.

It follows these rules:
If in State A and read on tape:
0 => Print 1, Move Right, Change to State B
1 => Print 2, Move Left, Stay in State A
2 => Print 1, Move Left, Stay in State A

If in State B and read on tape:
0 => Print 2, Move Left, Change to State A
1 => Print 2, Move Right, Stay in State B
2 => Print 0, Move Right, Change to State A

BookOwl

MartinBraendli2 wrote:
novice27b wrote:
This is great, and I'm actually surprised you're the first person to do this.

A quick googling returns results where people say that regex itself is not turing complete (which is true in most cases), but it doesn't look like anyone has tried a repeated find-and-replace before.
Yeah, I was surprised myself not to find any results on that matter. Maybe I'll implement Brainflakes in RegEx. It should be a bit easier than I thought, now that i know that you can nest capturing groups. However, it would still be quite a challange.

I think that you are looking for are Semi-Thue Systems

who needs signatures

Discuss Scratch