Discuss Scratch
- Discussion Forums
- » Advanced Topics
- » Making Scratch a Turing Tarpit
- ScratchMan544
- Scratcher
100+ posts
Making Scratch a Turing Tarpit
What is the minimal set of blocks required to make Scratch Turing complete?
Also, what is the minimal set of blocks required to have access to all the features of Scratch (Assuming we can create costumes, import sounds, as well as create variables and lists as much as we like)?
Also, what is the minimal set of blocks required to have access to all the features of Scratch (Assuming we can create costumes, import sounds, as well as create variables and lists as much as we like)?
_=(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] )
- Jonathan50
- Scratcher
1000+ posts
Making Scratch a Turing Tarpit
Really few.
NOTE: This is similar to https://scratch.mit.edu/discuss/topic/195968/ but it ISN'T a duplicate. There are different requirements.
when I receive [ v]That's all.
broadcast [ v] and wait
() + () :: stack
[] = [] :: stack
add [] to [ v]
replace item ( v) of [ v] with []
item ( v) of [ v] :: stack
NOTE: This is similar to https://scratch.mit.edu/discuss/topic/195968/ but it ISN'T a duplicate. There are different requirements.
Last edited by Jonathan50 (Oct. 28, 2016 02:41:00)
Not yet a Knight of the Mu Calculus.
- ScratchMan544
- Scratcher
100+ posts
Making Scratch a Turing Tarpit
Really few.when I receive [ v]
broadcast [ v] and wait
() + () :: stack
[] = [] :: stack
add [] to [ v]
replace item ( v) of [ v] with []
When you pressed the green flag, nothing would happen because you had no start script. If you added the [when green flag clicked] block then you could make scripts run. But is that turing complete? Because there's no way to subtract…
Last edited by ScratchMan544 (Oct. 27, 2016 06:20:51)
_=(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] )
- Jonathan50
- Scratcher
1000+ posts
Making Scratch a Turing Tarpit
[when green flag clicked] block then you could make scripts run.Oh. Whether it is necessary or not is debatable. You can click on a script. ¯\_(ツ)_/¯ When you pressed the green flag, nothing would happen because you had no start script. If you added the
But is that turing complete? Because there's no way to subtract…There is:
add (5) to [minuend v]I haven't tested it, but if the lists MINUEND, SUBTRAHEND and DIFFERENCE are empty, and if you run the first script, the first item of DIFFERENCE should be 3 (5 - 2).
add (2) to [subtrahend v]
add (0) to [difference v]
broadcast [subtract v] and wait
when I receive [subtract v]
replace item (1 v) of [difference v] with (item (1 v) of [minuend v])
broadcast [helper v] and wait
when I receive [helper v]
broadcast <(item (1 v) of [subtrahend v]) = [0]> and wait
when I receive [false v]
replace item (1 v) of [difference v] with ((item (1 v) of [difference v]) + (-1))
replace item (1 v) of [subtrahend v] with ((item (1 v) of [subtrahend v]) + (-1))
broadcast [helper v] and wait
Edit: It works
Last edited by Jonathan50 (Oct. 27, 2016 07:06:23)
Not yet a Knight of the Mu Calculus.
- BookOwl
- Scratcher
1000+ posts
Making Scratch a Turing Tarpit
You probably need Really few.when I receive [ v]That's all.
broadcast [ v] and wait
() + () :: stack
[] = [] :: stack
add [] to [ v]
replace item ( v) of [ v] with []
NOTE: This is similar to https://scratch.mit.edu/discuss/topic/195968/ but it ISN'T a duplicate. There are different requirements.
when green flag clickedalso. (when gf clicked to start, and delete all to get back to the starting state.)
delete (all v) of [list v]
who needs signatures
- CodeLegend
- Scratcher
500+ posts
Making Scratch a Turing Tarpit
You could even have an unlimited amount of conditionals by broadcasting <=>+(some even number). This could also be used for a repeat until, so I'd say that this system is definitely Turing-complete. (except that you forgot (item () of [])).broadcast <(item (1 v) of [subtrahend v]) = [0]> and wait
EDIT: Pesky []
Last edited by CodeLegend (Oct. 27, 2016 13:13:44)
- CodeLegend
- Scratcher
500+ posts
Making Scratch a Turing Tarpit
Nah. You can run scripts without using the flag. And deletion isn't necessary, replacement is sufficient. You probably needwhen green flag clickedalso. (when gf clicked to start, and delete all to get back to the starting state.)
delete (all v) of [list v]
- -Io-
- Scratcher
1000+ posts
Making Scratch a Turing Tarpit
Much simpler way:[when green flag clicked] block then you could make scripts run.Oh. Whether it is necessary or not is debatable. You can click on a script. ¯\_(ツ)_/¯ When you pressed the green flag, nothing would happen because you had no start script. If you added theBut is that turing complete? Because there's no way to subtract…There is:add (5) to [minuend v]I haven't tested it, but if the lists MINUEND, SUBTRAHEND and DIFFERENCE are empty, and if you run the first script, the first item of DIFFERENCE should be 3 (5 - 2).
add (2) to [subtrahend v]
add (0) to [difference v]
broadcast [subtract v] and wait
when I receive [subtract v]
replace item (1 v) of [difference v] with (item (1 v) of [minuend v])
broadcast [helper v] and wait
when I receive [helper v]
broadcast <(item (1 v) of [subtrahend v]) = [0]> and wait
when I receive [false v]
replace item (1 v) of [difference v] with ((item (1 v) of [difference v]) + (-1))
replace item (1 v) of [subtrahend v] with ((item (1 v) of [subtrahend v]) + (-1))
broadcast [helper v] and wait
Edit: It works
((5)+(-2))
You forgot to add item () of [] to the list too :P
- jokebookservice1
- Scratcher
1000+ posts
Making Scratch a Turing Tarpit
But what if you want to do 5 - VAR then you are forced to do the method metioned
- ScratchMan544
- Scratcher
100+ posts
Making Scratch a Turing Tarpit
[when green flag clicked] block then you could make scripts run.Oh. Whether it is necessary or not is debatable. You can click on a script. ¯\_(ツ)_/¯ When you pressed the green flag, nothing would happen because you had no start script. If you added theBut is that turing complete? Because there's no way to subtract…There is:add (5) to [minuend v]I haven't tested it, but if the lists MINUEND, SUBTRAHEND and DIFFERENCE are empty, and if you run the first script, the first item of DIFFERENCE should be 3 (5 - 2).
add (2) to [subtrahend v]
add (0) to [difference v]
broadcast [subtract v] and wait
when I receive [subtract v]
replace item (1 v) of [difference v] with (item (1 v) of [minuend v])
broadcast [helper v] and wait
when I receive [helper v]
broadcast <(item (1 v) of [subtrahend v]) = [0]> and wait
when I receive [false v]
replace item (1 v) of [difference v] with ((item (1 v) of [difference v]) + (-1))
replace item (1 v) of [subtrahend v] with ((item (1 v) of [subtrahend v]) + (-1))
broadcast [helper v] and wait
Edit: It works
Oh yeah! This reminds me of the lambda calculus, where we create the predecessor function P using the successor function S in a similar manner.
[EDIT: Never mind, this is different…]
Last edited by ScratchMan544 (Oct. 27, 2016 18:58:49)
_=(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] )
- CodeLegend
- Scratcher
500+ posts
Making Scratch a Turing Tarpit
I know that this has been addressed, but… What if you wanted to do (5)-(-2)? Much simpler way:((5)+(-2))
- ScratchMan544
- Scratcher
100+ posts
Making Scratch a Turing Tarpit
Actually, a+b is a - (0-b) so you can replace addition with subtraction and still have it be Turing-complete!
_=(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] )
- Jonathan50
- Scratcher
1000+ posts
Making Scratch a Turing Tarpit
Sorry, that was a mistake. I fixed it now. (except that you forgot (item () of []))
Last edited by Jonathan50 (Oct. 28, 2016 02:41:18)
Not yet a Knight of the Mu Calculus.
- -Io-
- Scratcher
1000+ posts
Making Scratch a Turing Tarpit
You can use list reporters and add a minus to the beginning of a number, the same way you join strings to bypass the 10240 char limit. But what if you want to do 5 - VAR then you are forced to do the method metioned
I'm kinda cheating with letter of and delete of, but really, they're essential for string manipulation, and I don't want to play with char[]-like structures. This one isn't possible without both of them, since you can't convert strings to char[].
when I receive [start v]Demo project: https://scratch.mit.edu/projects/127949334/
delete (all v) of [vars v]
add [123] to [vars v] // 123
add [] to [vars v] // Remember you can't replace a non-existing item.
broadcast [negate v] and wait
replace item (1 v) of [vars v] with [-321] // -321. Works with negative numbers
broadcast [negate v] and wait
broadcast (<(item (4 v) of [vars v])=[]>+(4)) and wait // This is because, for some reason,
// the broadcast block ends before the negated number can be added to the list
when I receive [negate v]
delete (all v) of [negate v]
replace item (2 v) of [vars v] with [1]
broadcast (<(letter (1) of (item (1 v) of [vars v]))=[-]>+(0)) and wait
when I receive [0 v]
add [-] to [negate v]
broadcast (<(letter (item (2 v) of [vars v]) of (item (1 v) of [vars v]))=[]>+(2)) and wait
when I receive [1 v]
replace item (2 v) of [vars v] with [2]
broadcast (<(letter (item (2 v) of [vars v]) of (item (1 v) of [vars v]))=[]>+(2)) and wait
when I receive [2 v]
add (letter (item (2 v) of [vars v]) of (item (1 v) of [vars v])) to [negate v]
replace item (2 v) of [vars v] with ((item (2 v) of [vars v])+(1))
broadcast (<(letter (item (2 v) of [vars v]) of (item (1 v) of [vars v]))=[]>+(2)) and wait
when I receive [3 v]
add (negate) to [vars v]
when I receive [4 v]
add ((item (3 v) of [vars v])+(item (4 v) of [vars v])) to [return v]
// -123 + 321 = 198
when I receive [5 v]
broadcast (<(item (4 v) of [vars v])=[]>+(4)) and wait
- ScratchMan544
- Scratcher
100+ posts
Making Scratch a Turing Tarpit
We could just switch to just using subtraction. x - (0 - y) == x + y.
_=(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] )
- Discussion Forums
- » Advanced Topics
- » Making Scratch a Turing Tarpit