An Algorithm/Turing machine
Produces a symbol from a finite alphabet, and continues doing so
infinitely.
Another algorithm gets a copy of this symbol,
Can this algorithm be so designed that it can tell weather the sequence
being generated is random.
My question in general is how does one define a "Random sequence" if we can define such a sequence at all
This of course depends on your definition of "random".
Is 12345678901011121314151617181920212223... random (notice the pattern)? This depends on what properties you want a random string of symbols to have. For some normality is enough. The above sequence is normal in base 10 for example, but it has a pattern, so maybe we will say it is not random.
Hence, we would like to consider even more statistical properties that a random string should have. For example it should satisfy the law of the iterated logarithm.
If we take this too the extreme, we could require that a random string satisfies all probability one properties. However, this is too strong. One of those properties is that this string can't be $x$, where $x$ is the sting in question. So in this sense there are no random strings.
Nonetheless, there is a way to take a step back and consider only those strings which pass all "computable statistical tests". Such a sequence is called "algorithmically random". This is not a well-defined term until one clarifies what they mean by "computable statistical test". The two most common such notions of algorithmic randomness are Schnorr randomness and Martin-Löf randomness.
Both of these notions require (among much stronger properties) that the string is not computable. Hence a string outputed by a deterministic Turing machine cannot be, say, Martin-Löf random. Also, it is not possible to determine in a finite number of steps if a string is random. For example, consider a string that starts with a large number of 0's and then behaves randomly. This should still be random because maybe you got a little lucky.
This "luck factor" can be quantized as the randomness deficiency of the string. More formally it is the maximum (over numbers $n$) of $n - K(x \upharpoonright n)$ where $K(x \upharpoonright n)$ is the Kolmogorov complexity of the first $n$ digits of the 0-1 string $x$. A Martin-Löf random string $x$ is one with finite randomness deficiency (so you were not infinitely lucky).
If one wants to check for sequences that have just really high randomness deficiency (say over 1000), this is semi-computable, that is one can determine when a string has high deficiency (very likely not random), but not necessarily determine when it has low deficiency. Just wait until one finds an initial segment of $x$ with low Kolmogorov complexity.
Schnorr randomness also has a notion of randomness deficiency, but it is not as clearly defined and depends on a particular statistical property being tested. It however has the advantage that there is an algorithm which computes the randomness deficiency of all strings with a small chance of error.
There is a whole subject devoted to algorithmic randomness, including two books:
