Skip to content

Partial | Semi-decidable etc.

September 12, 2010

I left maths after graduating many decades ago from university. I have been in computing for a couple of decades now. Coming back to maths after being away for so long is a bit of getting used to, like learning to walk again. I mean, terminologies seem to fly off above me, I know I have heard of certain terms but you only harbor vague and fuzzy notions about them. For example, people talk about First Order Logic (FOL) and how it is undecidable, so I get to believe it not knowing that there are a few nuances about this truth that I am not aware of.

So when someone speaks of a logical system having “partial” decidability, like other computing folk who are into practicalities, I get confused and I say to myself, partial decidability is actually the same as undecidability, no? The answer it turned out to be, no.

For example, FOL is in general undecidable if it is used in its full power, but there are toned down FOL theories which are decidable! If one does not use all the features of FOL, then one can arrive at a theory still classified under FOL, yet is decidable. For example, the field of real numbers
\langle \mathbb{R}, +, \times,^{-1},0,1\rangle
is said to be decidable.

Even my talking to other fellow computerists (my label for computer science folk) about some decidable FOL based theories get them confused too. The problem is in learning things by quick rules of thumb such as associating FOL with undecidability, always. May be it is just me, but I think some computerists are like me in this respect. So the computerist like me get thrown off his/her horse, when he/she encounters a curved idea, like partial decidability etc.

This has forced me to be aware that sometimes terms are not used precisely and so precision is a good thing, but I do not have much of it. Even my professor (who I still work with for new research projects) say that I am not very precise when it comes to my ideas. Being a “big” idea generalist has some disadvantages. The moral of the story is to be aware of some lack of precision in terminologies used by people out there and work on my being precise myself too.

No comments yet

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: