You are using a browser not supported by the Wolfram Cloud
Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.
I understand and wish to continue anyway »
WOLFRAM NOTEBOOK
In[]:=
MultiwayCombinator[{s[x_][y_][z_]x[z][y[z]],k[x_][y_]x},s[s[s[s][s]]][s][s][k],10,"StatesGraph"]
Out[]=
MultiwayCombinator[{s[x_][y_][z_]x[z][y[z]],k[x_][y_]x},s[s[s[s][s]]][s][s][k],6,"StatesGraph"]
In[]:=
Graph[MultiwayCombinator[{s[x_][y_][z_]x[z][y[z]],k[x_][y_]x},s[s[s]][s][s][s][s],14,"StatesGraph"],AspectRatio1]
Out[]=
In[]:=
Graph[MultiwayCombinator[{s[x_][y_][z_]x[z][y[z]],k[x_][y_]x},s[s[s]][s][s][s][s],14,"EvolutionEventsGraphStructure"],AspectRatio1]
Out[]=
In[]:=
ggg=MultiwayCombinator[{s[x_][y_][z_]x[z][y[z]],k[x_][y_]x},s[s[s[s][s]]][s][s][k],10,"StatesGraphStructure"]
Out[]=
In[]:=
Graph[ggg,VertexLabels(#ByteCount[#]&/@VertexList[ggg])]
Out[]=
Note the superexponential growth: presumably the combinator states get longer....
Amazingly, this terminates.....
Normal Forms for S Expressions
Normal Forms for S Expressions
Simpler Symbolic Systems
Simpler Symbolic Systems
Page 102
Page 102
[[ This is the Church numeral for 2 ; and for Church numerals, application is exponentiation ... hence e[e][e].... is the nested exponential ]]
Always give fixed points...
Always give fixed points...
Interpretation as numbers
Interpretation as numbers
e is just doing exponentiation with 2s
Simplest Universal Combinator
Simplest Universal Combinator
https://www.wolframscience.com/nks/notes-11-12--testing-universality-in-symbolic-systems/
Prove universality by showing reduction to S, K
Prove universality by showing reduction to S, K
Can there be a universal combinator with e[x_][y_] ...?
Can there be a universal combinator with e[x_][y_] ...?
Single Variable Cases
Single Variable Cases
[[[ Watch out for locally scoped pattern vars ]]]
Consider innermost and outermost strategies....
Consider innermost and outermost strategies....
When these systems are confluent, can adopt any evaluation strategy.....