Re: 'Recursively enumerable' sets

On Jun 5, 5:42 pm, Timothy Murphy <gayle...@xxxxxxxxxx> wrote:
MoeBlee wrote:
My definition of a partial recursive function is in terms of a
Turing
machine,

Perhaps it would be better to use the ordinary definition of 'partial
recursive function', which is an inductive definition that carves out
a proper subset of the set of number-theoretic functions.
...
why do you think your definition is better?

I explained why. One is a definition of 'recursive' (and all the
variations) and the other is a definition of 'Turing computable' (and
all the variations). These are two DIFFERENT definitions of two
DIFFERENT notions; THEN we prove that they pick out the same set. And
as a matter of ordinary mathematical presentation, 'recursive
function' is not defined as 'Turing computable' but rather through
some treatment as I described, and THEN the two are proven equivalent.
On the other hand, to just DEFINE 'recursive' as 'Turing computable'
misses the whole point or PROVING the equivalence, especially as that
proof is a central basis for Chuch's thesis.

Again, it seems to me much easier to describe Church's thesis -
which is only a matter of opinion as far as I can see

It's a matter of opinion in the sense that it is an informal thesis
and not a theorem. But that does not detract from its importance and
centrality in the subject.

in terms of Turing machines.

Some people may well agree with you on that point, including those who
are adamament that it should not be called 'Church's thesis' but
rather 'the Church-Turing thesis' (or even better 'the Turing-Church'
thesis (shades of Paul McCartney now wanting the songs to be called
'McCartney-Lennon' songs rather than as present 'Lennon-McCartney'
songs) or 'Turing's thesis?). However, my point is not as to what
makes the thesis easier to state, but rather that the equivlance of
recursiveness with Turing computability is often considered among the
main REASONS for adopting the thesis or at least a good part of an
argument in its favor (also added is that the lambda calculus,
Kleene's equations, Post computability, Markov algorithms, register
machines, etc. are also equivalent in this sense). And that is only
PART of the importance of understanding the equivalence between
recursion and Turing computability.

Further, I don't know the orginal poster's purposes in having a
definition, so I can't say definitively as to what is best for him
(thus I originally said "PERHAPS it would be better to use the
ordinary defintion" [emphasis added]). But if the purposes include
(not necessarily in order of importance) (1) communicating with other
people in the field and (2) fully understanding the central concerns
and results in the field, then I suggest that he understand that
'recursive' (and its variants) is not ordinarily defined through
Turing machines, but rather, ordinarily, it has an inductive
definition having to do with certain functors (such as composition,
recursion, and minimization) regarding the number theoretic functions.
And in that regard, it should be pointed out that defining
'recursive' (and its variants) through Turing machines is not as
IMMEDIATE as the ordinary definitions, since not only does the
definition of 'Turing machine' need to be formulated but ALSO the
definition of 'the number theoretic function computed by a Turing
machine'.

So I do suggest that it is best to know the ordinary definitions of
'primitive recursive', 'partial recursive' and 'total recursive' and
ALSO to understand that the ordinary definitions are equivalent to the
definitions couched in terms of Turing machines, as especially that is
a CENTRAL result of the field of study. To just define
'recursive' (and its variants) in terms of Turing machines and not to
understand recursive functions in terms of primitive recursion (the
base functions and closed under composition and recursion) and
minimization is to be cut off from a huge portion of subject.

In my view, most of logic is much more easily understood
when expressed in terms of Turing machines,
rather than in the disgusting languages developed by logicians.

"Disgusting languages". Oy vey. It's not just a matter of what is more
easily understood but also of a greater context of various related and
even equivalent concepts. And the fact simply is that 'recursive' is a
concept that came before the Turing machine, and it is of GREAT
notability that the two concepts turn out equivalent. To eschew (as
"disgusting") the definition of 'recursive' in number-theoretic terms
is simply to cut one's self off from the heart of the subject matter.

I don't actually consider your definition of a recursive function
to be "disgusting"

One's aesthetic evaluation of certain formulations may be worth
consideration in certain contexts, but your blanket dismissmal - "the
disgusting languages developed by logicians" - strikes me in this
context as silliness at best and intellecual bigotry at worst.

just more or less irrelevant
to the study of recursive enumerability.

I find such remarks puzzling. I take it that you are a professor of
mathematics, thus vastly beyond me in your knowledge and understanding
of mathematics. Yet, the ordinary definition of 'recursively
enumerable' is not irrelevent to the study of recursive enumerability.
The connections among the concepts of well ordering, induction,
recursion, Turing computability, and such things as formal languages
are mathematically and philosophically profound.

I'm even quite rusty in a lot of the particulars of the study of
recursion and computability (indeed, I may demure from spelling out
certain formulations as I may not be content with the degree of
precision I can produce off-the-cuff in a post), but in this specific
context you're coming across as verging on strident in your opinions
that actually amount to closing off avenues of investigation, while
these are avenues that have already proven to have rich rewards (as if
you are saying "Don't even bother going up the avenue of the ordinary
definition of recursive functions; it's irrelevent"). The original
poster is well served by knowing the ordinary definitions of
'recursive' (and its variants) not just because they are the ordinary
definitions and thus allow him to converse more exactly with other
people, but the ordinary definitions serve the purpose of keeping a
notable distinction which even sets up the revealing result that the
approachs are extensionally the same.

Actually I think it _is_ a matter of what is more easily
understood,
at least when one is teaching a subject.

And I did not discount ease of understanding. I said that it should
not be a matter of JUST ease of understanding. And there is not ease
of understanding here that would justify cutting off a central part of
the study. Moreover, it is not even given that Turing computability
(and semi-computability) of a number theoretic function is easier to
understand than the inductive definition of 'recursive function' and
'semi-recursive function'. I surely would prefer to take a course in
this subject that INCLUDES understanding the fascinating connections
between the concepts of recursion and Turing computability rather than
one that excludes (on the basis of a hopelessly subjective view that
logicians have devised "disgusting" languages) such knowledge that is
not only required for passing an examination for further research in
the field but that is so very intellectually rewarding onto itself.

MoeBlee


.

Relevant Pages

  • Re: What does recursive or recursively enumerable literally mean?
    ... I begin to read a couple of books on Turing Machine and I ... I'm not familiar with the term "Turing recognizable" although ... |a variant of TM called enumerator, which was still hard to understand. ... For example, the word 'recursion' in algorithm, e.g. the ...
    (comp.theory)
  • What does recursive or recursively enumerable literally mean?
    ... I begin to read a couple of books on Turing Machine and I ... meaning of both Turing-recognizable and Turing-decidable since the word ... a variant of TM called enumerator, which was still hard to understand. ... For example, the word 'recursion' in algorithm, e.g. the ...
    (comp.theory)
  • Re: a language is a language
    ... Turing-complete (it forbids general recursion, ... Not for me :-) No Turing completeness, no programming language. ...
    (comp.programming)
  • Re: Recursive Call
    ... >>> standards, both direct and indirect recursion is prohibited. ... >> COBOL, but I did find it extremely useful in writing a parts explosion ... Stack machines really have proven their worth over non-stack machines. ...
    (comp.lang.cobol)
  • Re: Recursive Functions
    ... >> Computing integer powers of numbers is fairly common in scientific ... >> programming, and is one of the relatively few things missing from C used ... Some processors do recursion faster ... version given by Knuth, on Pentium-class machines. ...
    (comp.lang.c)