3 ms·
What you're talking about can be formalized via https://en.wikipedia.org/wiki/Arithmetical_hierarchy#The_arithmetical_hierarchy_of_formulas https://en.wikipedia
by dooglius 7y ago
What you're talking about can be formalized via https://en.wikipedia.org/wiki/Arithmetical_hierarchy#The_arithmetical_hierarchy_of_formulas https://en.wikipedia.org/wiki/Arithmetical_hierarchy#The_ari...
where your notion of "computable" likely corresponds to some set between (Sigma_1 intersect Pi_1) and (Sigma_1 union Pi_1) depending on some nuance. In any case, you can show by diagonalization that there are statements strictly outside these sets--that is, first order propositions that cannot be verified or refuted by computer.
- vanderZwan 7y agoI cannot pretend to truly follow the actual mathematics you linked and summarized (I appreciate the attempt!), but the conclusion in the last sentence answers my intended question. Thank you!
- lonelappde 7y agoIt's a mistake though. Humans can't prove any of those propositions either.
- vanderZwan 7y agoOh. That's kinda typical, hahaha. I guess this topic can get quite subtly and tricky, even for trained mathematicians?
- lonelappde 7y agoThe question was whether there are statements provable by humans but not computers, which is either trivially impossible or guaranteed, depending on whether you allow the computer to use the same axioms as the people.
- dooglius 7y agoIt depends on how you interpret it, I interpreted it as asking if there are provable statements that can't be "computed" directly.
- vanderZwan 7y agoUh... well... can I claim the "sorry, not a mathematician so my reasoning about these matters is quite sloppy, relatively speaking"-defense? (The responses here have been very nice despite that though, thank you everyone!)