Peter Leupold

100 Actions

 2018 May 31 reviewed Approve Is the halting problem solvable for NPDAs? May 31 comment Is the halting problem solvable for NPDAs? Summarizing: I think I provide strong evidence that the question is decidable, but I do not provide a definite method. In the transformations, one does not detect whether "useless" loops in the PDA/grammar would halt or not - they are simply eliminated, all of them. May 31 comment Is the halting problem solvable for NPDAs? Sorry, re-reading everything I find that my answer is not completely answering your question. I say that it is decidable whether for a given NPDA there exists an equivalent one that always halts. But probably this is always true, because there is e,g. Greibach NF for all context-free languages. But you ask about a given PDA, not about whether a halting one exists for the same language. Thus for an answer to your question, one might have to analyze which kind of thing the mentioned grammar transformations eliminate and what that means in terms of PDAs. May 30 answered Is the halting problem solvable for NPDAs? Apr 25 answered Turing machine - compare two words Apr 9 comment Language whose intersection with a CFL is always a CFL @Kai: $L$ is indeed context-free, but it is not regular, while the claim in the OP is that every context-free language fulfilling the stated conditions must be regular. So $L$ is a counterxample to that claim. Apr 9 answered When are two CFG's different? Mar 29 comment One counter automaton as a function Well, you would have to specify how exactly the automaton counts. At any rate, a deterministic one counter automata should be able to do everything your devices do, definitely your two examples. If equivalence is decidable for them, then it is decidable for your model, which is weaker or at most equivalent. Mar 29 comment One counter automaton as a function I think "equivalence" would be better than "equality". The latter means completely equal, the former means they compute the same function. Here you can find some info on the decidability of equivalence: cstheory.stackexchange.com/questions/6948/… Mar 14 comment Automaton without stack for visibly pushdown languages Have you tried writing an eMail to the author? She should know more about this than anyone else. Mar 10 answered Regular grammar with at most one c Mar 9 awarded Yearling Mar 8 comment Can we see all of mathematics as an attempt to simplify computations? I have quite a clear understanding of what hypercomputation means. It refers to models of computation that are more powerful than (or uncomparable to) Turing Machines. So you are not using "computable" in a more general sense, just with reference to a different model of computation. We could also use FA-computable (instead of regular) or PDA-computable (instead of context-free) to refer to computabilities weaker than Turing-computability. My comments are true for any of these computabilities, independent of their power. Mar 8 comment Can we see all of mathematics as an attempt to simplify computations? I think that my comment is absolutely independent of what model of computation you are talking about. A problem is either computable or not in the moment that the definition is clear. New theorems can only change our knowledge concerning this (non-)computability, but not the (non-)computability as such. Just like the finding of a solution to a famous problem does not change the fact that whether such a solution exists. Mar 8 comment Can we see all of mathematics as an attempt to simplify computations? Theorems cannot "turn incomputable algorithms into computable algorithms;" they may find or help formulate a (computable) algorithm for a problem, for which formerly no (computable) algorithm was known. But this knowledge has nothing to do with the computability of the problem. You would have to use the term computable in the sense of "computable according to the current state of knowledge," which is not its common usage. Mar 8 comment Church-Turing thesis and hypercomputation? Well, if Penrose argues that the mind is not computable, that implies an answer to your question, because our minds are parts of the universe. So if there is some processes in our mind, which cannot be computed, there are some processes in the universe, which cannot be computed. In "Shadows of the Mind" Penrose first gives a rather mathematical proof for the existence of this kind of process; in a second part he goes into physics and speculates why and where this non-computability may come from. Jan 3 comment Why full Chomsky hierarchy is so detailed, if there are decidable recursive languages? Parsing in polynomial time has been one of the central requirements for formalisms modelling natural language. Exponential time is thought to be too much even for the human brain, That is why the recursive and also the context.sensitive languages are not considered good models. For the mildly context-sensitive models polynomila time parsing is one of the central requirements. Nov 15 answered Find a grammar for this language Sep 21 answered Does intersecting the output of 2 programs give the output of another program? Sep 20 comment Is mathematics context-free? Well. If you look at the axioms as strings of a formal language, nothing about possible derivations is specified. Or, if you want to take the axioms as rules, are all the occurring symbols non-terminals Then what are the terminals and the terminal strings? The answer to your question will depend much on the technical details of how you "derive" the grammar from the axioms. That is why it is impossible to answer the question as it is stated.