/sci/ - Science & Math » Thread #11688462

77KiB, 1228x344, Comp.png

View Same Google iqdb SauceNAO

Computability Theory, Proof theory, Completeness

Anonymous Tue 19 May 11:05:24 2020 No.11688462 View Reply Original Report

Quoted By: >>11688506 >>11691101

Computability Theory, Proof theory, Completeness

Anonymous

Anonymous Tue 19 May 2020 11:38:52 No.11688506 Report

Quoted By: >>11689513 >>11691662

>>11688462
Homework questions belong on the homework board >>>/hm/

Anonymous

Anonymous Tue 19 May 2020 18:07:36 No.11689513 Report

Quoted By:

>>11688506
fpbp

Anonymous

Anonymous Wed 20 May 2020 01:31:27 No.11691101 Report

Quoted By:

>>11688462
Here is a lemma that makes this problem trivial.
Show that $\emptyset^{(\omega)}$ is Turing equivalent (it is in fact recursively isomorphic but Turing equivalence is sufficient) to $\text{Th}(\mathfrak{N})$ , where $\emptyset^{(\omega)}=\{\langle i,n\rangle~|~i\in \emptyset^{(n)}\}$ . Here $\langle \cdot, \cdot\rangle$ is a computable bijection between $\omega^2$ and $\omega$ , and $\emptyset^{(n)}$ is the nth iterated of the Turing jump. One direction is trivial and the other uses prenex normal form of an arithmetical sentence, and the Post Hierachy theorem that relates Turing jumps to arithmetical sets.

Anonymous

Anonymous Wed 20 May 2020 05:28:12 No.11691662 Report

Quoted By:

>>11688506
true, take it over there plz I'm tired of seeing stuff like this here

Anonymous

Anonymous Wed 20 May 2020 19:08:12 No.11693527 Report

Quoted By:

Bumpin for computability theory

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches