Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

What area of computer science for this?

  1. Nov 21, 2013 #1
    Lately I'm interested in questions like this: -
    Given a set of commands, what all computation problems can be done?

    For e.g.: - SQL has a fixed set of instructions like select, from, where etc. You can only do a limited amount of things with this language. Since there are no for loops and stuff, you are constrained.

    So what area of computer science deals with questions like this?
  2. jcsd
  3. Nov 21, 2013 #2
  4. Nov 21, 2013 #3

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Theory of computation.
  5. Nov 21, 2013 #4
    I looked it up. Automata theory is what I'm looking for, I guess.
    Wikipedia says it is the study of abstract machines and the computational problems that can be solved using these machines.
    When it says 'abstract machines', it means some specific language or a set of instructions right?
  6. Nov 21, 2013 #5


    User Avatar
    Science Advisor
    Homework Helper

    Start from the beginning. Google "Turing".
  7. Nov 21, 2013 #6
    I know about Turing and Turing-completeness. It decides if a given language is complete (i.e. computational problems can be solved using it or not)
    But does theory of computation take languages like SQL and see if they are complete. If incomplete, then does it try to find out what all things can it do?

    Anyways, I'll look for a book on it and see what it covers. Thank you for guiding!
  8. Dec 6, 2013 #7


    User Avatar
    Gold Member

    Incidentally, SQL does have loops that can be made to act identically to FOR loops. It is generally considered to be a fairly complete procedural language.
  9. Dec 7, 2013 #8

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    In fact, SQL is Turing complete. See http://blog.coelho.net/database/2013/08/17/turing-sql-1/ [Broken].
    Last edited by a moderator: May 6, 2017
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook