The passage about algebraically closed fields is correct but easy to be mislead by: the characteristic is not specified, so the theory ACL of algebraically closed fields does not decide, for example, the sentence "$\forall x(x+x=0)$." So ACL is indeed an example of an incomplete-but-decidable theory.
What is true is that ACL$_p$ - the theory of algebraically closed fields of characteristic $p$, for $p\in\{$primes$\}\cup\{0\}$ - is complete and decidable.
EDIT: The statement "$T$ does not decide $\varphi$" is potentially ambiguous, as it has two reasonable interpretations:
Neither $\varphi$ nor $\neg\varphi$ is $T$-provable (in symbols: $T\not\vdash\varphi$ and $T\not\vdash\neg\varphi$).
There are models of $T$ in which $\varphi$ holds, and there are models of $T$ in which $\varphi$ fails (in symbols: $T\not\models\neg\varphi$ and $T\not\models\varphi$).
Luckily, by the completeness theorem (see below) these two interpretations are equivalent. Note that this is a peculiarity of first-order logic; for this reason, it's good to avoid saying "$T$ decides $\varphi$" when discussing non-first-order logics unless one has already specified what this means.
I believe the above will resolve your question, but just for completeness (hehe) let me end by summarizing the situation:
Any recursively enumerably axiomatizable theory which is complete is also decidable (just search through proofs). However, a complete theory need not be decidable - e.g. $Th(\mathbb{N};+,\times)$ ("true arithmetic") is complete ($Th(\mathcal{M})$ is always complete, for any structure $\mathcal{M}$) but not decidable.
- Incidentally, by Craig's trick a theory is r.e.-axiomatizable iff it is recursively axiomatizable.
First-order logic is (sound and) complete, in the following sense: for any set of sentences $\Gamma$, a sentence $\varphi$ is true in every model of $\Gamma$ if and only if there is a proof of $\varphi$ from $\Gamma$. In symbols, $$\Gamma\models\varphi\iff\Gamma\vdash\varphi.$$ The right-to-left direction is basically trivial; the left-to-right direction takes work.
For the first question, I'll give a proof with about the same level of rigor as the notion of "behavior" of a computable function. Without a slightly firmer definition, there's not much more to be done. Indeed, as Noah pointed out in the comments, for sufficiently loose definitions of "behavior", the theorem becomes false. This sounds like rice's theorem, and so I will basically reproduce a proof of that.
As you've noticed, behavior is a more general condition than halting. So we want to imitate the proof that $\mathsf{Halts}$ is undecidable and see what happens. The biggest issue is that we cannot directly plug our function into itself for a contradiction. We will need the following fact:
Enumerate the turing machines as $\mathsf{TM}_n$. For every computable $Q(x,y)$, there is an $e$ so that $\mathsf{TM}_e(y) = Q(e,y)$.
That is, the $e$th turing machine is the same as $Q(e,-)$. This theorem is commonly used in diagonalization arguments with turing machines, and it's a good one to have in your back pocket.
Let $f$ be a computable function, and $b$ be a behavior that we want it to have. We claim there is no function $B$ so that $B(f) = 1$ if and only if $f$ behaves like $b$.
Indeed, towards a contradiction say $B$ exists. We will assume the behavior is nontrivial. That is, we can find functions $f$ and $g$ which do, and don't, satisfy the behavior. Then we can define a new function $\mathsf{UhOh}$ as follows:
$$\mathsf{UhOh}(x,y) = \begin{cases} g(y) & B(\mathsf{TM}_x) \\ f(y) & \lnot B(\mathsf{TM_x}) \end{cases}$$
Note, as in the solution to the halting problem, that $\mathsf{UhOh}$ does the opposite of its input. That is, $$B(\mathsf{UhOh}(x,-)) \iff \lnot B(\mathsf{TM}_x).$$
Do you see contradiction around the bend? Let's use the theorem cited above! We know there is some $e$ so that $\mathsf{TM}_e(y) = \mathsf{UhOh}(e,y)$. Now, we ask the question: $B(\mathsf{TM_e})$?
$$B(\mathsf{TM_e}) \iff B(\mathsf{UhOh}(e,-)) \iff \lnot B(\mathsf{TM}_e)$$
UhOh indeed.
Thankfully, the second question is much easier. We want to know that "$h(x)$ is undefined" is not a semidecidable thing to check.
Recall that "$h(x)$ is defined" is a semidecidable thing to check. This is because if $h(x)$ is defined, then its computation will halt in say, $N$ steps. Then by waiting long enough we can check that $h(x)$ is defined.
Now we remember the following fact: Whenever $P$ and $\lnot P$ are semidecidable, they must both be decidable. This is because we can run our semideciders for $P$ and $\lnot P$ in parallel, and we know that one of them will give us an answer. But once we've answered, one, we've answered both!
So if "$h(x)$ is undefined" were semidecidable, then "$h(x)$ is defined" would be decidable. But this is obviously false (cf. the halting problem).
(Notice that while we contradict by using the halting problem, this is not a reduction to $\mathsf{Halts}$.)
I hope this helps ^_^
Best Answer
I'm not totally sure what you're asking, but let me take a stab at it:
Your sentence
is absolutely correct. There are many senses in which two decision problems can be "equivalent," and the point is that semidecidability (or more commonly, computable or recursive enumerability) does not always respect these notions. For instance, every c.e. set is Turing equivalent to a co-c.e. set, but obviously no c.e. set is also co-c.e. unless it is computable. This is essentially the example you give of unsatisfiability for first-order formulas.