Halting problem uses a trivial construction of undecidability. My intuition is that "nontrivially undecidable" does not exist
-
-
Replying to @BagelDaughter
The Arithmetic Hierarchy gives an infinite hierarchy of classes of undecidability harder than halting. Are all 'trivial'?
1 reply 0 retweets 2 likes -
Replying to @FrameOfStack
no, not "trivial". But, "contrived"? Not increasing the risk that I will stumble upon an undecidable problem by chance?
1 reply 0 retweets 0 likes -
-
Replying to @FrameOfStack @BagelDaughter
How about these? https://en.m.wikipedia.org/wiki/List_of_undecidable_problems …
1 reply 0 retweets 2 likes -
Replying to @FrameOfStack
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
1 reply 0 retweets 0 likes -
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 @FrameOfStack
I think I'd be satisfied with 2 if X is of substantial consequence elsewhere in the field
1 reply 0 retweets 0 likes -
-
Replying to @MoralOfStory @FrameOfStack
yes, when originally formulating the question, I thought of that as being highly likely to halt (and be false)
1 reply 0 retweets 0 likes
basically I was looking for something like P=NP that didn't have a very clearly likely answer
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.