I'm not familiar enough with group theory or topology to comment on those. Among the rest, it seems to break down into 2 forms
-
-
Replying to @BagelDaughter @FrameOfStack
1. Instantiate the halting problem in X. (trivial) 2. X produces pseudorandom behavior which can't be predicted. (maybe not)
2 replies 0 retweets 0 likes -
Replying to @BagelDaughter
Instantiating the halting prob. can be how you *prove* undecidability in probs of interest for other reasons; I've seen that.
1 reply 0 retweets 1 like -
Replying to @FrameOfStack
in those cases I always feel let down because the halting problem usually isn't a "pragmatic" usage of a system
2 replies 0 retweets 0 likes -
Replying to @BagelDaughter @FrameOfStack
One practical example is that you cannot write a truly optimal compiler. https://en.wikipedia.org/wiki/Full_employment_theorem …
1 reply 0 retweets 0 likes -
Although you may think that cases to worry about are rather pathological.
1 reply 0 retweets 0 likes -
Replying to @ValidOfPriors @FrameOfStack
Yes, actually compilers are one of the motivators for my intuition
1 reply 0 retweets 0 likes -
sophisticated manipulation of programs in turing complete language, switching b/w representations, it all works
1 reply 0 retweets 0 likes -
decidability plays little role in compiler construction, infinite loops/recursion come up but are trivial bugs
1 reply 0 retweets 0 likes -
Example: http://compilers.cs.ucla.edu/popl16/popl16-full.pdf … is surprising because it should be undecidable
1 reply 0 retweets 1 like
actually v. relevant to my rambling, it shows how to work around the "diagonalization gadget" of halting prob.
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.