Thanks for your reply. I understood lot better than I was previously. So summing up your answers, A language is turing complete, if we can write infinite loops and primitive recursive function..... Some of the non turing complete languages that I came across are HTML, CSS, SQL... From this can I assume, that a language is turing complete, if it computes something, rather than just trying to display a interface, or pull records..... Coz languages like HTML CSS doesnt do anything to compute something, it just transforms one way of representation to another(HTML -> browser readable code), where as C,C++ can compute something and can represent large mathematical problems..... Am I right.... Pardon me if my question is stupid... Thanks..
On Mar 27, 4:07 pm, Wladimir Tavares <[email protected]> wrote: > Theoretically, a language is Turing-complete if it computes all partial > recursive functions, ie functions that include all the basic functions and > is closed under composition, primitive recursion and minimization. > > Basic Functions > zero () = 0 > succ (x) = x +1 > proj_i (x1, x2,..., xn) = xi > > Composition > Let f1, f2, f3, fn eg partial recursive functions then h is defined by a > composition iff h (x1,..., xn) = g (f1 (x1, .., xn), f2 (x1, ... , xn ),..., > fn (x1,..., xn)) > > The notion of computability is established by Churh-Turing thesis. I believe > our general computability is a very difficult task:) > > Wladimir Araujo Tavares > *Federal University of Ceará > > * > > On Sun, Mar 27, 2011 at 3:56 PM, Carl Barton > <[email protected]>wrote: > > > > > > > > > To elaborate why; if your language suffers from the halting problem then > > it's pretty safe to say it's turing complete and infinite loops would allow > > you to achieve that. > > > On 27 March 2011 19:03, Carl Barton <[email protected]> wrote: > > >> If you're not concerned about being that formal then having conditional > >> branching statements and being able to write infinite loops would be a > >> pretty good indication. > > >> On 27 March 2011 14:38, Karthik Jayaprakash > >> <[email protected]>wrote: > > >>> Hi, > >>> Thanks for replying. I am aware of that. But is there a practical > >>> way of checking it???? > > >>> On Mar 26, 7:40 pm, Carl Barton <[email protected]> wrote: > >>> > If it can simulate a universal turing machine then it is turing > >>> complete > > >>> > On 26 March 2011 22:34, Karthik Jayaprakash < > >>> [email protected]>wrote: > > >>> > > Hi, > >>> > > Is there a way to check that if a language is Turing complete????? > > >>> > > Thanks. > > >>> > > -- > >>> > > 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. > > >>> -- > >>> 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. > > > -- > > 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. -- 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.
