Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [diagonalization]

The tag has no usage guidance.

2 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3 votes
0 answers
31 views

Understanding a black-box vs white-box simulation and relativization

I am trying to understand the relativization barrier from Baker Gill Solovay (BGS). About this barrier, I have heard that it only applies when using a black-box simulation. Hence, my question is, what ...
441Juggler's user avatar
1 vote
0 answers
92 views

The role of diagonalization - asymmetry between TM and Recursion Theory

This might be a slightly strange or irrelevant question. My apologies if it is. I'll try to formulate it the best I can. First, here is an hypothesis: diagonalization is syatematically used to prove ...
Hugolin Bergier's user avatar