Michael, (01)
The word 'decidable' has been bandied about in contexts that are
far removed from its original definition. Many of those extensions
are convenient and useful. But the word should always be used with
all the proper qualifications. (02)
Unfortunately, it has been used in confusing ways as a mantra for
declaring some kinds of things good or bad. People who have no idea
how the term is defined have been using it in ways that are hopelessly
wrong and counterproductive. (03)
JFS
>> But every major programming language since 1945 has been undecidable,
>> and no programmer would ever want less expressive power. (04)
MB
> What do you mean with "undecidable" ? That the halting problem is undecidable
>? (05)
Yes. That is the only precise definition that has ever been given
for that word. But the word 'decidability' has been applied to many
different kinds of things. (06)
Fundamental definition: A procedure P, as stated in some formal
language L, is said to be *undecidable* for some data D iff it is
impossible to prove whether P will come to a halt in processing D
or whether it will continue forever (AKA "get hung up in a loop"). (07)
If it can be proved that P will come to a halt on D, then P is
said to be *decidable* for input data D. Note that a procedure
can be decidable for some data, but undecidable for other data.
for example, a procedure on a relational database can be decidable
and efficient, but it might be undecidable for other kinds of data. (08)
I used the word 'procedure' instead of 'algorithm'. Some computer
scientists say that the word 'algorithm' should only be used for
procedures that can be proved to halt with the desired solution to
some problem. To avoid that issue, I'll use the word 'procedure',
which may or may not halt. (09)
The distinction of decidable/undecidable, which is properly defined
for procedures, can be extended to many other things, and each
extension must be carefully evaluated: (010)
1. Problems: Procedures (or algorithms) can be used to perform
some useful service, such as solving a problem. The word
'decidable' can be extended to problems: (011)
A problem X is said to be *decidable* iff there exists some
procedure (or algorithm) P that can be proved to solve X --
ie, P is given a statement of X as its input data D, and it
is decidable that P will halt on D with the solution to X. (012)
Note that a problem X might be solved by many different
procedures, some of which may be decidable while others are
undecidable. Sometimes an undecidable procedure Q can be more
efficient for solving X than a decidable procedure P. In that
case, it may be a good idea to start by running Q for a short
time T. If Q doesn't halt within time T, then use P. (013)
2. Programming languages: Many kinds of languages are used to
express procedures and algorithms. A *decidable* programming
language L is one that cannot be used to specify procedures
that are undecidable -- i.e., no program stated in L will ever
get hung up in a loop. (014)
The constraint of decidability is very drastic, since it makes
it impossible to state a huge number of important algorithms
that are decidable. But some specialized languages can be
decidable and useful for a very narrow range of tasks. (015)
Every major programming language is undecidable. But programmers
have developed methodologies for writing efficient and decidable
procedures. Examples include structured programming and design
patterns. There are many variations of these methodologies. (016)
3. Logic languages: Properly speaking, no version of logic can state
a procedure. Therefore, the notion of decidability has no direct
extension to logics. However, a combination of a logic with some
computational procedure can be used for some kinds of tasks. But
what is decidable is always the *combination* of a logic with a
particular kind of procedure for a particular kind of task: (017)
(a) Proving theorems: A logic plus a proof procedure can be used
to test whether a particular statement is can be derived from
other statements (which may be called axioms). (018)
(b) Answering questions: A logic plus a proof procedure plus some
given data can be used to derive answers from the data. This
kind of problem is similar to the task of proving theorems,
if the axioms are equated with the data. However, the data
may be in a specialized form, such as a relational database
or a triple store. For such data, the task of answering
questions may be decidable when task (a) is undecidable. (019)
(c) Constraint testing: A logic can be used to state constraints
on permissible data. The task is of verifying whether the
constraints are true of some data is closer to (b) than to (a). (020)
(d) Induction or data mining: Deduction is only one way of using
logic, and it requires a prior set of axioms before it can be
used. The task of induction or data mining is to analyze the
given data to form generalizations, which may later be used
for other tasks, which may include (a), (b), or (c). (021)
(e) Abduction: Another important way of using logic is to form
hypotheses about a given set of data. These hypotheses are
often much more complex (or "insightful") than induction.
The methods of abduction are related to what would be called
"creative" in humans, and no formal specification is possible.
However, the hypotheses generated by abduction can and should
be tested against the data by other methods, such as (a) or (b). (022)
Given this range of uses for logic, the term 'decidable' can only be
applied to a logic when a specific kind of task for a specific kind
of data is being considered. (023)
> A decidable programming language would not be Turing complete and IMO should
> not be called a programming language. Are regular expressions a programming
> language ? Only in a very broad sense. (024)
The word 'programming language' has been applied to so many different
kinds of computer languages that I don't believe that a precise formal
definition is possible or desirable. (025)
Regular expressions are a good example. They are declarative statements
which could be considered a kind of logic, but they can also be used
as procedures when they are combined with a suitable processor. (026)
In fact, many programming languages include methods for using regular
expressions. Some languages, such as AWK, use regular expressions
as their primary notation. And AWK is Turing complete, since it
has enough facilities for storing intermediate data to enable it
to simulate a Turing machine. (027)
> But that programming languages should be undecidable does not automatically
> mean that logics should be undecidable. Don't you compare apples and oranges
> here ? (028)
Yes. The above discussion shows that the term 'decidable' can only be
applied to a logic language in a very indirect way. It is so indirect
that it's more misleading than useful to say that a certain logic
language is decidable or undecidable. That decision *always* depends
on what you plan to do with the logic. (029)
I discuss these and related issues in the following paper: (030)
http://www.jfsowa.com/pubs/fflogic.pdf
Fads and fallacies about logic (031)
John (032)
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J (033)
|