so what I'm saying is that with a suitable translation, there are physical things that represent TMs
-
-
Replying to @ReferentOfSelf @ModelOfTheory
or computable bit strings. But I don't know how to represent a halting oracle as anything meaningful
1 reply 0 retweets 0 likes -
Replying to @ReferentOfSelf
How about a TM that runs all TMs and writes 1 on nth output bit when nth TM halts? Halting oracle is limit of output tape.
1 reply 0 retweets 1 like -
Replying to @ModelOfTheory
I'll have to think about whether that satisfies. I'm not sure whether the fact that this TM doesn't show that anything...
1 reply 0 retweets 0 likes -
-
Replying to @ReferentOfSelf
Of course, this only works for Delta^0_2. The arithmetical hierarchy goes a lot higher.
1 reply 0 retweets 0 likes -
Replying to @ModelOfTheory
after thinking, my main problem with your suggestions is that they are two different mathematical objects...
1 reply 0 retweets 0 likes -
Replying to @ReferentOfSelf @ModelOfTheory
you can't replace one with the other in proofs, though maybe you'd be able to adapt the proofs
1 reply 0 retweets 0 likes -
Replying to @ReferentOfSelf
I'm not sure what you mean. What are the two mathematical objects?
1 reply 0 retweets 0 likes -
Replying to @ModelOfTheory
Subset of N which are codes for TMs that halt vs TM that runs TMs until they halt and output 1 at that code
1 reply 0 retweets 0 likes
Infinite string of 1s is different from TM that writes inf string of 1s, but you suggested using latter to represent former.
-
-
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
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.