What does 'recursive' or 'recursively enumerable' literally mean?
- From: "Federico Magallanez" <steganographer@xxxxxxxxx>
- Date: 27 Aug 2005 17:46:50 -0700
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.)
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.
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'?
.
- Follow-Ups:
- Re: What does 'recursive' or 'recursively enumerable' literally mean?
- From: Keith Ramsay
- Re: What does 'recursive' or 'recursively enumerable' literally mean?
- Prev by Date: Re: Question on another GRE Comp Sci problem (Turing Machine stuff...)
- Next by Date: Re: What does 'recursive' or 'recursively enumerable' literally mean?
- Previous by thread: Question on another GRE Comp Sci problem (Turing Machine stuff...)
- Next by thread: Re: What does 'recursive' or 'recursively enumerable' literally mean?
- Index(es):
Relevant Pages
|