Results 1 to 4 of 4

Math Help - complexity theorie, deterministic turing-machines, time complexity

  1. #1
    Newbie
    Joined
    Nov 2011
    Posts
    7

    complexity theorie, deterministic turing-machines, time complexity

    Be A = { A_n | n \in N} a countable set of Stockitems. and
     (Frml)_A = { φ | φ is a formula with stockitems of A. }

    Find a finite alphabet Σ, a embedding i : Frml_A --> Σ*
    and a deterministic n^k - time- turing machine M (for adequate k \in N, so A(M) = {i(φ|φ \in Frml_A }.

    A rough sketch of the turingprogramm is enough. I have to give an estimation up for the runtime of my program.

    Can someone help me, I dont even know how to start this exercise

    Every help would be appreciated
    Last edited by suslik; December 19th 2011 at 06:55 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: complexity theorie, deterministic turing-machines, time complexity

    I am not sure what the following things mean: stockitems, A(M) and i(φ). It is better to give too much explanation than not enough, keeping in mind that notations and definitions in complexity theory and logic in general vary widely between courses and textbooks.

    This question belongs in the Logic section of the forum.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2011
    Posts
    7

    Re: complexity theorie, deterministic turing-machines, time complexity

    i'm sorryy. can i displace it to the logic section?

    A(M) means M accepts A , if A(M) .Its acceptionset.. M is my Machine.
    i is the embedding i: Frml_A --> Σ*
    I think its the same if I take f: Frml_A --> Σ* and A(M) = {f(φ) | φ \in Frml_A

    ok Stockitem it's "Satzsymbol" in German, I think its the right translation but not for maths I dont know the english word. Its like a variable e.g. A_0 \wedge A_1 . A_i is a Satzsymbol.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: complexity theorie, deterministic turing-machines, time complexity

    Quote Originally Posted by suslik View Post
    can i displace it to the logic section?
    You can send a private message to a moderator (their list is at the bottom of each forum section).

    Quote Originally Posted by suslik View Post
    ok Stockitem it's "Satzsymbol" in German, I think its the right translation but not for maths I dont know the english word. Its like a variable e.g. A_0 \wedge A_1 . A_i is a Satzsymbol.
    It probably means a "propositional variable" in English.

    Since the set of propositional variables is countable, they can be encoded with binary numbers. So, to encode A_5 you can have, for example, the string A_101_ where '_' is a delimiter. Logic connectivesó \land, \lor, \to and \negócan be included in the alphabet Σ.

    It is somewhat easier to check if a string is (an encoding of) a well-formed formula if the formula is written in prefix (Polish) or postfix (reverse Polish), rather than the usual infix, notation because prefix and postfix notations don't need parentheses. The algorithm for evaluating (or checking) an expression in prefix notation is roughly described in Wikipedia. If one has a stack, then it is possible to scan an expression only once to check whether it is well-formed. From here, one can argue that one needs polynomial time.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Turing machines and decidability.
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: November 29th 2010, 01:38 PM
  2. Turing machines with a single tape.
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 15th 2010, 07:41 AM
  3. O(sin n), Ω(sin n), Θ(sin n) complexity
    Posted in the Advanced Math Topics Forum
    Replies: 4
    Last Post: August 18th 2010, 07:55 AM
  4. Complexity of Algorithm
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: June 21st 2008, 11:13 AM
  5. Turing Machines
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 19th 2007, 04:39 PM

/mathhelpforum @mathhelpforum