An Undecidable Problem in SIP
blog.marc.petit-huguenin.org
An Undecidable Problem in SIP
1–4 of 4 posts
Re: An Undecidable Problem in SIP
#2Even 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?
Re: An Undecidable Problem in SIP
#3I 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?
Re: An Undecidable Problem in SIP
#4Its not NP to determine if the max-forward reach zero. Just simulate it until it reaches zero or not... QED