Re: What does 'recursive' or 'recursively enumerable' literally mean?
- From: "Keith Ramsay" <kramsay@xxxxxxx>
- Date: 28 Aug 2005 09:47:54 -0700
Federico Magallanez wrote:
|Recently, I begin to read a couple of books on Turing Machine and I
|must admit that they are wheting my curiosity. Mostly, I read Prof.
|Sipser's book 'Introduction to the Theory of Computation.' After my
|rather hasty and narrow observation, I found that the textbooks on TM
|can be categorized into two kinds;one prefers the term
|'Turing-recognizable' and 'Turing-decidable' while the other
|'recursively enumerable' and 'recursive.' (Prof. Sipser follows the
|former.)
I'm not familiar with the term "Turing recognizable" although
it makes sense. I've seen "recursively enumerable" much more
often. There's a third set of terms, "computably enumerable"
and "computable", which I'm told are becoming more popular.
|Although I am not a native English speaker, I can easily catch the
|meaning of both Turing-recognizable and Turing-decidable since the
word
|'recognize' and 'decide' in textbook holds a quite obvious meaning as
|in a colloquial use. However, the meaning of 'recursively-enumerable'
|or 'recursive' eludes me.
Being a native English speaker doesn't help very much here,
since "recursive" is a technical term. :-)
|Prof. Sipser's book actually tries to explain 'why recursively
|enumerable is synonymous with Turing-recognizable' using the concept
of
|a variant of TM called enumerator, which was still hard to understand.
|Moreover, the textbook does not contain any explanation on "why
|recursive has the same meaning as Turing-decidable" (as far as I
|searched). For example, the word 'recursion' in algorithm, e.g. the
|definition of Fibonacci numbers, is quite lucid; recur means 'to
happen
|or appear more than once' and it makes sense in this context. However,
|I cannot find any clue in the case of computation theory. Is there any
|book or reference that clarifies the relationship between 'recursive'
|and 'Turing-decidable'?
The notion of "recursive function" was one of a handful of
notions that were shown afterward to be equivalent to each
other. The reason for the term "recursive" is presumably
because they are defined as the functions that can be
constructed by a certain kind of function definition, where
recursive definitions similar to the one defining the
Fibonacci numbers play a key role.
One can show that Turing computable and recursive are the
same class of functions by showing how to simulate each
kind of computation with the other one. Given a construction
of a recursive function, one can program a Turing machine
to compute the same function by manipulating expressions
on its tape. Given a Turing machine that computes a total
function, one can define the function it computes as a
recursive function by encoding the state of its tape at
each step as a number and defining functions for making
the transition at each step.
Keith Ramsay
.
- References:
- What does 'recursive' or 'recursively enumerable' literally mean?
- From: Federico Magallanez
- What does 'recursive' or 'recursively enumerable' literally mean?
- Prev by Date: What does 'recursive' or 'recursively enumerable' literally mean?
- Next by Date: Roots of a polynomial
- Previous by thread: What does 'recursive' or 'recursively enumerable' literally mean?
- Next by thread: Roots of a polynomial
- Index(es):
Relevant Pages
|
