= 27d567bc2d48d9f40e9ccc20ea370b15)
gRR comments on Formulas of arithmetic that behave like decision agents - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (33)
Huh? Of course, there is - the Universal Turing Machine. You were probably thinking of the halting problem, but here we can just assume every function halts.
[The agent idea was naive though. I was young and stupid when I wrote the grandfather comment :)]
The agent described in the OP is definitely not a Turing machine that halts.
Hmm. The agent is a recursive function, so it is equivalent to a Turing machine that halts, no?
But I see your point. There is no simple formula, so if nothing else, it's inelegant.
Whoops! I said in the OP that the precursor to A (before diagonalization) is a recursive function, but it's not. It's not computable because it has to check whether several propositions are theorems of Peano arithmetic, and also because of that existential quantifier in the definition of A. If A itself were recursive, then it would provably (in PA) cooperate or defect; but it cooperates or defects unprovably (in PA). I'll edit the OP to make it correct.
The rest of the post still works because all the functions are representable — they can be represented by formulas in arithmetic — even if they're not recursive. Thanks for bringing this to my attention.
EDIT: Oy, they're not even "representable" in the technical sense. They're only definable.