complexity theorie, deterministic turing-machines, time complexity

Be A = {$\displaystyle A_n$ | n $\displaystyle \in$ N} a countable set of Stockitems. and

$\displaystyle (Frml)_A $ = { φ | φ is a formula with stockitems of A. }

Find a finite alphabet Σ, a embedding i : $\displaystyle Frml_A $--> Σ*

and a deterministic $\displaystyle n^k$ - time- turing machine M (for adequate k $\displaystyle \in$ N, so A(M) = {i(φ|φ $\displaystyle \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 :)

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.

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: $\displaystyle Frml_A$ --> Σ*

I think its the same if I take f: $\displaystyle Frml_A$ --> Σ* and A(M) = {f(φ) | φ $\displaystyle \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. $\displaystyle A_0 \wedge A_1 $ . $\displaystyle A_i$ is a Satzsymbol.

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. $\displaystyle A_0 \wedge A_1 $ . $\displaystyle 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 $\displaystyle A_5$ you can have, for example, the string A_101_ where '_' is a delimiter. Logic connectives—$\displaystyle \land$, $\displaystyle \lor$, $\displaystyle \to$ and $\displaystyle \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.