You can't if you are trying to print a binary representation. This extends to any integer base. The binary representation of an irrational square root never repeats or terminates. That's why it's called irrational!. So there can exist no machine the prints it exactly.
You can however: 1) design a machine that prints 1 (base sqrt(2)) for the square root of 2. But in the same number system, integers are not going to generally have finite representations, so you are just shifting the problem. 2) design a machine that prints the square root of 2 to any arbitrary precision in any integer base. The length of the string is countably infinite and recursively enumerable! Now for the transendental numbers (like pi and e), even 1) gets tougher! On Dec 5, 5:01 am, saurabh singh <[email protected]> wrote: > I was wondering can we design a machine(Even hypothetical) that can find a > *perfect square root *of any integer thats given to it. > My logic why we can't is since there are uncountably infinite real numbers, > there will be uncountably infinite numbers requiring infinite states on a > turing machine.But since there are only finite number of states,we cant > make such a machine.And since we cant make a turing machine for calculating > the square root we cant make any computing machine for the same. > I am not sure about my logic though.Thats why i have this doubt. > > -- > Saurabh Singh > B.Tech (Computer Science) > MNNIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
