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

Be A = { | n N} a countable set of Stockitems. and
= { φ | φ is a formula with stockitems of A. }

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

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

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.

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: --> Σ*
I think its the same if I take f: --> Σ* and A(M) = {f(φ) | φ

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. . is a Satzsymbol.

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).

Originally Posted by suslik

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. . 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 you can have, for example, the string A_101_ where '_' is a delimiter. Logic connectives— , , and —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.