When our two-state PDA constructed from CFG is non-deterministic PDA?

We can always convert our GNF-CFG/CNF-CFG to a two-state PDA but i’m wondering when our PDA is non-deterministic? i’m sure we can not make DPDA for non-Deterministic-CFL , and i suspect that same rule which applied for differing between DCFG and non-Deterministic-CFG also applied here. i mean when we have non-Deterministic δ (delta) implied non-Deterministic edge in our PDA. if my suspicion is right , then for every DCFL exist at least one DPDA. Am i right?

R ≝ Production Rules of CFG (x,y,"LBL") is a labeled-edge between x and y with “LBL” as a label  ∀r∊R: r= (A,aⱰ) ( A∊V ⋀ a∊T ∧ Ɒ∊V*) add (q,q,"a,A/Ɒ") to E Add (q,q,"ε,z/Sz′") to E Add (q,f,"ε,z′/z′") to E 

enter image description here

If anything can be verified efficiently, must it be solvable efficiently on a Non-Deterministic machine?

Suppose, I wanted to verify the solution to $ 2$ ^$ 3$ . Which is $ 8$ .

The $ powers~of~2$ have only one 1-bit at the start of the binary-string.

Verify Solution Efficently

n = 8 N = 3 IF only ONE 1-bit at start of binary-string:   IF total_0-bits == N:    if n is a power_of_2:      OUTPUT solution verified, 2^3 == 8 

A solution will always be approximately $ 2$ ^$ N$ digits. Its not possible for even a non-deterministic machine to arrive to a solution with $ 2$ ^$ N$ digits faster than $ 2$ ^$ N$ time.

Question

Can this problem be solved efficently in non-deterministic poly-time? Why not if the solutions can be verified efficently?

Does this imply Hamiltonian path cannot be decided in nondeterministic logspace?

Suppose I nondeterministically walk around in a graph with n vertices.

When looking for a Hamiltonian path, at some point I’ve walked n/2 vertices.

There are (n choose n/2) different combinations of vertices I could have walked (meaning the unordered set, not the ordered walk).

Each of those states must be distinct from one another.

If not, then, depending on the remaining n/2 vertices, I would decide the wrong answer.

Therefore, midway through my processing, at n/2, I need (n choose n/2) different states. That is too big for logspace.

Therefore you cannot decide a Hamiltonian path by nondeterministically walking around.

Does this imply Hamiltonian path cannot be decided in nondeterministic logspace – at least by “walking around”?

Why aren’t distributed computing and/or GPU considered non-deterministic Turing machines if they can run multiple jobs at once?

So we know a nondeterministic Turing machine (NTM) is just a theoretical model of computation. They are used in thought experiments to examine the abilities and limitations of computers. Commonly used to dicuss P vs NP, and how NP problems cannot be solved in polynomial time UNLESS the computation was done on the hypothetical NTM. We also know an NTM would use a set of rules to prescribe more than one action to be performed for any given situation. In other words, attempt many different options simultaneously.

Isn’t this what distributed computing does across commodity hardware? Run many different possible calculations in parallel? And the GPU, does this within a single machine. Why isn’t this considered an NTM?

Statement TRUE or FALSE: there exist more non-deterministic TMs than deterministic TMs

Statement TRUE or FALSE:

There exist more non-deterministic TMs than deterministic TMs

For my point of view (I ask if it’s correct):

Under the assumption $ P \neq NP$ , the Statement is TRUE because (1) P is a subset on NP and (2) P is a special case of non-determinism.

Under the assumption $ P = NP$ , the Statement is FALSE, because for each deterministic TM we have a non-deterministic TM.

Can a Non-Deterministic Pushdown Automata recognize $ \# a^nb^{2^n} \# $ which a TM can?

$ \# a^nb^{2^n} \# $

such that

• The alphabet of the machine is {, a, b, x}.

• The symbol x will never appear on the input a.

• The contents of the tape at completion may be anything.

• The head begins on the lefthand #.

• n ≥ 0.

I know that a Turing machine could recognize this language. But can a NPDA recognize this language too? I am thinking it can but I do not know how to start proving how/why?

Converting non-deterministic algorithm to deterministic

I was thinking about an non-deterministic algorithm to generate all the subsets of the $ \{1..n\}$ set.

Subsets(n)     S' = null     for i = 1..n             u = choice(1..n)         if u in S'            fail         S' = S' + u     for_each u in S'          print u 

How would I convert this algorithm into a deterministic form? I know that it is a lot more complicated to convert the choice statement in a deterministic manner but I want to get a general idea about maybe representing it in a deterministic manner.

motivation and idea of defining non-deterministic Turing machine

This is a very basic question but I spent some time reading and find no answer. I am not computer science majored but have read some basic algorithm stuff, for example, some basic sorting algorithms and I also have some basic knowledge of how computers operate. However, I am really interested in the idea of a Turing machine, especially the non-deterministic one.

I have read Wiki about the definitions of a Turing machine (and watched some youtube videos) and I sort of accept that, although I really feel that this is a huge jump from an algorithm to an abstract machine. From my understanding (you are more than welcome to correct me):

  1. A Turing machine is a machine performing works specified on a cookery book (algorithm).
  2. The pages of the cookery book represent the “states” of your machine and each page contains a table saying that which state and which cell your machine will move to given the alphabet the machine read and your current state. (NB. This is not a function but a partial function because it is possible that the machine stops.)
  3. So, to guess the idea and motivation of defining an abstract Turing machine, I imagine that the algorithm corresponds to the partial map, the memory of the computer corresponds to the (infinitely long) tape and what’s finally on the tape is the answer to the question you wanna solve.

So, Turing machine looks like a machine to realize any algorithm to solve problems. One just “translates” any algorithm to a set of mysterious simple rules (i.e. the partial function) and let the machine do the laboring job and then we get the solution.

In this respect, Turing machine is always deterministic, because algorithms are deterministic. It tells you what to do next precisely. This is no uncertainty. Turing machine is just a machine to realize any algorithm.


OK, This is very abstract and I sort of accept it. However, then I read something called non-deterministic Turing machine (NTM) and then I was knocked down. A NTM is pretty much similar to a Turing machine except that the partial function is now replaced by a “relation”. That is, it is a one-to-multiple map and it is no longer a (partial) function.

Could someone explain to me why we need such multiple options? I would never expect to encounter something uncertainty in the implementation of an algorithm. It is like telling the machine: you first do A, then if you find yourself in a state B and find the data is now B’ then you choose for yourself one of the 10 allowed next steps?

Are NTM’s corresponding to a set of algorithms that need uncertainty? for example the generation of random numbers? If no, why do we need to allow multiple choices for a Turing machine?

Any help will be appreciated!