# complexity theorie, deterministic turing-machines, time complexity

• December 19th 2011, 06:01 AM
suslik
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 (Speechless)

Every help would be appreciated :)
• December 19th 2011, 06:09 AM
emakarov
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.
• December 19th 2011, 06:27 AM
suslik
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 (Rofl) I dont know the english word. Its like a variable e.g. $A_0 \wedge A_1$ . $A_i$ is a Satzsymbol.
• December 19th 2011, 07:44 AM
emakarov
Re: complexity theorie, deterministic turing-machines, time complexity
Quote:

Originally Posted by suslik
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
ok Stockitem it's "Satzsymbol" in German, I think its the right translation but not for maths (Rofl) 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.