1
$\begingroup$

I've been wondering how an argument that a solution to a particular problem doesn't exist is put together.

For instance "Pour-El and Richards found an ordinary differential equation $\phi'(t)=F(t,\phi(t))$ with $F$ computable and no computable solution."

Another puzzling example is the non-computability of Chaitin's constant.

I'm not talking about trivial examples, e.g. the DE $f(x)=f(x)+1$.

Could you give examples of outlines of such proofs? The only strategy I can think of is showing that the assumption that a solution exists leads to a contradiction, but surely there are more sophisticated ways than this?

EDIT: In case it wasn't clear (it probably wasn't), I also would examples of proof strategies involved in proving the non-existence of solutions to, for instance, DEs. The reason my examples focuses on computability is because I couldn't find any examples of the non-existence.

$\endgroup$
3
$\begingroup$

It sounds like you're asking how you tell that a given object (solution to a DE, Chaitin's constant, etc.) is not computable, not that it doesn't exist. Indeed, the point is that these things do exist, and can be proved to be pretty weird. So let me talk a bit about how you show that something is not computable.

The easiest way to show that a function $f$ is incomputable is to exhibit - for each computable function $c$ - a value $n$ such that $f(n)\not=c(n)$. For example, let $\varphi_i$ be some canonical listing of all partial computable functions, and define $f(n)$ to be $\varphi_n(n)+1$, if $\varphi_n(n)$ is defined, and $0$ otherwise. Then immediately by definition $f$ is not computable!

Sometimes the argument along these lines is more involved - for instance, to show that the halting function $g$ (given by $g(n)=0$ if $\varphi_n(n)$ is defined, and $1$ otherwise) is not computable, we need to talk about constructing machines: if such a $g$ were computable, it would be $\varphi_k$ for some $k$. Now show that there is a computable $j$ such that $\varphi_j(i)$ is $1$ if $\varphi_k(i)=0$ and is undefined otherwise, and think about $\varphi_j(j)$ . . .

There is also coding. If I've already shown that some $f$ is not computable, then I can show that a function $\hat{f}$ is not computable by "reducing" $f$ to $\hat{f}$: showing how I can compute $f$ "relative to" $\hat{f}$. Since $f$ is not computable, neither is $\hat{f}$. This can be made precise - see "oracle Turing machines."

$\endgroup$
  • $\begingroup$ @Thanks for the reply! I don't have any upvotes left for today, but I'll make sure to send you one your way! I have a question though: You say that $f(n)=\phi (n)+1$ if $\phi(n)$ is defined and $0$ otherwise, with the point (I guess) that $f(n)$ is always different from any $c(n)_n$ and because all the $c(n)_n$'s form a complete list of all computable functions, $f(n)$ is not computable? Is this correct? If so, that seems arbitrary, as you'd never be able to write down such a list? And I am also very interested in the non-existence of solution to DE's, so feel free to write about them as well! $\endgroup$ – Bobson Dugnutt Feb 22 '16 at 18:22
  • $\begingroup$ @Lovsovs That's right, but there are lists of all (partial) computable functions - this is a crucial point in computability theory! We can't tell which ones are total, but we can effectively list all the partial ones. While this $f$ is indeed somewhat artificial, it's still an important example - and an important tool for showing that other functions aren't computable (via reduction as mentioned in my last paragraph). I don't know much about differential equations in computability, but if I think of anything I'll add it. $\endgroup$ – Noah Schweber Feb 22 '16 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.