3 ms·
An Undecidable Problem in SIP
- zitterbewegung 12y agoEven 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?
- userbinator 12y agoI think this article is a bit alarmist... 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?
- tlarkworthy 12y agoIts not NP to determine if the max-forward reach zero. Just simulate it until it reaches zero or not... QED