This is a wonderful video. The exposition is precise, understandable, and easy to listen to. Learned a lot as someone with a math undergrad and just a cursory understanding of computability theory. Keep it up!
Right now, my own work is related to Weihrauch degrees rather than Turing degrees, but the basic ideas are similar. It's funny you mention forcing, since that has also been on my todo list for a while
There are tons of interesting degree structures! If you don't mind, can you give a quickly explain what Weihrauch degrees are or link to an introduction? I haven't been able to make sense of what I've been able to find online.
Have you ever considered doing a full series from the basics up until incompleteness or maybe even independence of CH? You would follow some text start from first order logic. up until incompleteness and then do some model theory. up until independence of CH.
Probably not as a full series, but I have done Gödel's Incompleteness Theorem in videos 11 and 12 of my Regular Languages and Model Theory series (and will again when I do Hilbert's Tenth Problem), and I definitely do want to do some introductory logic videos. CH could be fun, but it's been ages since I've seen the proof, so I'd have to research it first.
Hi Thomas! While we can have oracles for arbitary explicit uncomputable functions f(x), don't we need to prove that f(x) is the solution to a undecidable problem P(x) ? to assume that O_P (x) is the oracle for P?
I'm not sure if you mean sum as functions or the Turing degree join operation, so I'll answer both. If we're talking sums of functions (f+g)(x) = f(x)+g(x): Let f be an arbitrary noncomputable function and g = 1-f. Then f and g are Turing equivalent, but f+g is just the constant 1 function, which is computable. If we're talking the join operation (f oplus g)(2x) = f(x), (f oplus g)(2x+1) = g(x), then yes. You can compute g from (f oplus g) (just enter the appropriate odd input), so if you can compute (f oplus g) from f, by transitivity, you can compute g from f.
This is a wonderful video. The exposition is precise, understandable, and easy to listen to. Learned a lot as someone with a math undergrad and just a cursory understanding of computability theory. Keep it up!
Interesting and well presented!
Right now, my own work is related to Weihrauch degrees rather than Turing degrees, but the basic ideas are similar. It's funny you mention forcing, since that has also been on my todo list for a while
There are tons of interesting degree structures! If you don't mind, can you give a quickly explain what Weihrauch degrees are or link to an introduction? I haven't been able to make sense of what I've been able to find online.
Have you ever considered doing a full series from the basics up until incompleteness or maybe even independence of CH? You would follow some text start from first order logic. up until incompleteness and then do some model theory. up until independence of CH.
Probably not as a full series, but I have done Gödel's Incompleteness Theorem in videos 11 and 12 of my Regular Languages and Model Theory series (and will again when I do Hilbert's Tenth Problem), and I definitely do want to do some introductory logic videos. CH could be fun, but it's been ages since I've seen the proof, so I'd have to research it first.
Hi Thomas!
While we can have oracles for arbitary explicit uncomputable functions f(x), don't we need to prove that f(x) is the solution to a undecidable problem P(x) ? to assume that O_P (x) is the oracle for P?
Oracle functions are allowed to be computable, even though they're useless in that case.
Is f + g only equivalent to one of f or g if the other of them is less or equally as powerful as the first?
I'm not sure if you mean sum as functions or the Turing degree join operation, so I'll answer both.
If we're talking sums of functions (f+g)(x) = f(x)+g(x):
Let f be an arbitrary noncomputable function and g = 1-f. Then f and g are Turing equivalent, but f+g is just the constant 1 function, which is computable.
If we're talking the join operation (f oplus g)(2x) = f(x), (f oplus g)(2x+1) = g(x), then yes. You can compute g from (f oplus g) (just enter the appropriate odd input), so if you can compute (f oplus g) from f, by transitivity, you can compute g from f.
@@trkern I was taking about the join operation
@@trkern Thanks