Q:

How pardoxes relate to a theory's decidability and completeness

Would "this sentence is false" make a theory containing it both undecidable & incomplete, while "this sentence is unprovable" make a theory containing it incomplete(syntatically) but not necessarily undecidable(semantic)?
It seems to me that there is no algorithm to decide if the first sentence is true, hence theory is undecidable, and it's not provable, hence the theory is incomplete.
Meanwhile, the truth of the second sentence seems decidable as true, while it can't be provable.

A:

No, there is not really a connection here.
You have to be careful: natural-language sentences generally aren't even expressible in a given formal framework, and even when they are they don't necessarily behave as expected.
For example - assuming we're looking at classical first-order logic - the sentence "This statement is false" is never expressible in any good sense; this is due to Tarski, and is essentially an elaboration of the liar paradox.
The sentence "This statement is unprovable" is a more interesting situation. First, we can't really just say "unprovable," we need to talk about unprovability relative to a specific theory; and that theory has to be reasonably nice for provability to be talked about internally. But it gets worse: consider the theory T = PA + "PA is inconsistent." T is consistent, incomplete, and undecidable (a good exercise - remember that PA doesn't prove its own consistency and is essentially incomplete) and yet T proves "For all p, T proves p" and so in particular T proves the statement

"The statement "This statement is T-unprovable" is false."

