Even though it seems that you can create pathological SIP rules that are undecidable could you reduce a subset of the problem if you are only allowed to do a set of forwards and then you have a graph where you can detect cycles with a simple cycle detection algorithm?
Now, let's say that we want to implement CTS in SIP. The CPL language is not powerful enough for that but we can define a very simple extension
...
And because we previously proved that SIP with CPL is Turing-Complete
...
Note that at least some SIP systems are not necessarily Turing-Complete - here we had to add an extension to our very limited system based on CPL to make it Turing-Complete.
In other words, he had to create a completely theoretical extension, which AFAIK doesn't actually exist, just to show that it could be Turing-complete? If there's a real extension in use or set of extensions that could make it Turing-complete, why didn't he just choose that?
3 comments
[ 9.4 ms ] story [ 776 ms ] threadNow, let's say that we want to implement CTS in SIP. The CPL language is not powerful enough for that but we can define a very simple extension
...
And because we previously proved that SIP with CPL is Turing-Complete
...
Note that at least some SIP systems are not necessarily Turing-Complete - here we had to add an extension to our very limited system based on CPL to make it Turing-Complete.
In other words, he had to create a completely theoretical extension, which AFAIK doesn't actually exist, just to show that it could be Turing-complete? If there's a real extension in use or set of extensions that could make it Turing-complete, why didn't he just choose that?