@gaditb personally whenever i make one of these i just add a vm instruction count limit and a stack/heap size limit and call it a day. but computing the actual space-time complexity… intriguing possibilities for websites. maybe you could have a bound on the amount of computation per output byte-ish and reject programs in advance??
after all, streaming the response would naturally dilute the time cost…