I'm having difficulty understanding the below.
Does this mean that the language L is an element of PCP which is made from two functions f(n) and g(n) which if there exists the polynomial time randomized oracle machine
- it takes input x and a random string r of big O of function f(n) where n is the size of the input
- theres a query set function Q (r,x) where r is the length, and x is the input, which produces several queries where the number of queries is the big O of the function g(n) - that is grows according to the growth size of g(n) depending on n
- where did y come from and what is it?
- makes a computation using the data and outputs My(r,x) which can either be 0 or 1.
is that correct? what is y please? and how is it used in the randomized oracle machine please
It's probably best to first understand NP in these terms, since most people have at least a decent intuition for what NP is. Informally, NP problems are ones whose solutions can be verified in polynomial time.
In this formalism, we say a language $L$ is in NP if there is a Turing machine such that for any string in $x\in L$ there is an oracle string $y,$ whose size is polynomial in the size of $x$ such that the machine will accept on inputs $x$ and $y$ in polynomial time and if $x\notin L$ there is no oracle string $y$ such that the machine accepts on $x$ and $y$.
Here the input string $x$ is the 'problem' and the oracle string $y$ is the 'solution', and the Turing machine verifies that $y$ is a solution to $x$ (i.e. a proof that $x\in L$) in polynomial time. To be more explicit the input strings under consideration could encode a weighted graph $G$ and a number $l$. The language $L$ could be the set of all strings that encode $(G,l)$ such that the graph $G$ has a Hamiltonian cycle of weight less than $l.$ So figuring out what strings are in $L$ is solving the traveling salesman problem. For any $(G,l)\in L,$ there is a string $y$ (given to us by the oracle) that encodes a hamiltonian cycle on $G$ of weight less than $l$ and we can computationally verify in polynomial time that this is indeed the case. In other words, the traveling salesman problem is NP.
In PCP the situation is slightly different. Now, we are not necessarily presented with a full solution/proof but we only can ask the oracle a limited amount of information about it (before, we just demanded that the length of $y$ be polynomial in the length of $x$, which always allowed us to get the full solution, for instance the size of the description of a Hamiltonian cycle scales at most with the number of vertices). However, we are also allowed to use a randomized algorithm with some bounded amount of randomness, and we only demand probabilistic guarantees on whether we decide an input $x$ correctly or not. As I mentioned in the comments, we demand that we verify with absolute certainty when $x\in L$ but we may have some false positives (up to $50\%$ of the time) when $x\notin L.$ (Of course these numbers can be generalized.) So our randomized Turing machine asks its allotment of questions to the oracle about its purported solution, then in polynomial time decides if it's 'right as far as we can tell'. We demand that for $x\in L$ there's always an oracle string that will convince our Turing machine, but when $x\notin L$ there may be oracle strings that fool our Turing machine into a false verification, but with low probability.
The most interesting case $PCP(\log(n),1)$ has query size $g(n)=1,$ which means our algorithm can ask only a fixed number of questions about the solution, no matter how large the problem is, and it is allowed a logarithmic number of random bits. The PCP theorem says that $ PCP(\log(n),1) = NP$. So for instance the traveling salesman problem is $PCP(\log(n),1).$ Which means that there are some numbers $M$ and $C$ such that there is a randomized algorithm that takes an instance $(G,l)$ of the traveling salesman problem with size $n$ and uses $C\log(n)$ random bits. We have an oracle that has a purported proof there is a Hamiltonian cycle of weight less than $l$, but we don't know if it really is one or not. The random algorithm asks the oracle $M$ yes or no questions about its purported proof, and then, in polynomial time, decides whether it believes the oracle or not. The algorithm will always accept if the oracle really has a valid proof, and will not accept with >50% probability of the oracle does not.
Note that NP is a special case of $PCP(f(n),g(n)$, the theorem notwithstanding. We can express the definition of NP I gave in the second paragraph as $PCP(0,\operatorname{poly}(n)),$ in other words there is a deterministic polynomial time algorithm that will check the solution/proof (using a polynomial number of queries, though that's all you could use in a polynomial amount of time anyway.)