Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am reading historical stuff on the algebraic and transcendental numbers. Descartes, in his Geometry, excluded all curves not expressible as algebraic equations. Later, Leibniz called such curves transcendental.

I wonder now which automata recognise exactly the algebraic numbers? As Turing showed, Turing machines can recognise all algebraic numbers. Apparently, finite state machines cannot recognise algebraic numbers. So, there must be an automata class between that does the job?

share|improve this question
3  
Among what numbers? What kind of input are you using? –  Qiaochu Yuan May 21 '12 at 15:29
    
The computable numbers are the real numbers computable by a Turing machine. So I am looking for something like "The algebraic numbers are the real numbers computable by ...". Basically, anything on the relation of algebraic numbers and automata would be of interest to me. –  corto May 21 '12 at 16:37
1  
@corto: Qiaochu probably means to ask how you code your inputs. A Turing machine, by definition, only accepts finite-length inputs so it cannot accept, say, the decimal representation of a real number as an input. If you are thinking of chaining Turing machines together then that won't work – Rice's theorem tells us that there can be no decision procedure for properties of outputs of Turing machines. –  Zhen Lin May 21 '12 at 18:02
    
@corto: a priori one must distinguish between "computable by" and "recognizable by." One is about outputs and one is about inputs. –  Qiaochu Yuan May 21 '12 at 18:30
    
I go for both..;) I would be just interested in any kind of information on the relation between algebraic numbers and automata theory. Can the algebraic numbers somehow be characterised by some automata class? If the question is trivial or too vague I would also be happy with some textbook.. It is just the case that I cannot find anything on this anywhere.. –  corto May 21 '12 at 18:42

1 Answer 1

http://rjlipton.wordpress.com/2009/02/24/a-conjecture-of-hartmanis/

Hartmanis' (conjectures that) if a number is easy to recognize, in a way to be made precise shortly, then it must be either rational or transcendental. It cannot be a proper algebraic number. This remains completely wide open.

The key is the notion of what it means to be “easy to recognize”. The formal notion is based on the notion of a real-time Turing Machine. A real number is computable in real-time if there is a multi-tape Turing machine that recognizes each digit in constant time. Thus, the {n^{th}} digit is recognized at time {O(n)}. Note, we insist that a stronger constraint is used: the gap between generating each digit is absolutely bounded by a constant {O(1)}.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.