Does turing completeness preclude a language from having a CFG? I couldn't find any paper saying that.
Can a Turing complete language ever have a CFG?
1.1k Views Asked by Bighted19 At
1
There are 1 best solutions below
Related Questions in PARSING
- TypeScript: Type checking while parsing an arbitrary JSON that is typed/
- How to have fixed options using Option.Applicative in haskell?
- How to convert mathematical expression to lambda function in C++?
- JsonObject throws an exception: JSONObject["employer_website"] is not a string (class org.json.JSONObject$Null : null)
- Trying to fix my c++ code for it to read the right amount of nodes from a file
- Selenium get page after "loading" page
- Parse tag in html via Google Sheets (importxml)
- FluentD / Fluent-Bit: Concatenate multiple lines of log files and generate one JSON record for all key-value from each line
- Editing non-String values in JComboBox
- Handling multiple errors in Bison parser
- Which is the most idiomatic way to parse an i32 from ascii in Rust
- I got this error from a JSON Validator - what does this mean?
- Conflict between lexer rules in ANTLR4 for Fortran grammar
- mqtt message parsing problem in a node.js
- How to print error code from URL response in swift
Related Questions in GRAMMAR
- Need clarification on pumping lemma for context free languages
- Grammar for combinations of Numpy arrays
- What is exactly Ruby's `not` keyword?
- VSCode Extension - Grammar Injection Into Multiple Languages
- Integrating Grammar/Spellcheck Tool in ASP.NET Application for Textarea
- Is the alternative operator in ABNF match first or longest?
- ANTLR4 matches to lexer rule instead of parser rule
- Distinguishing integer and decimal arithmetic with ohm.js
- Trouble with Island Grammar parsing unordered network configuration using Python textx
- ANTLR4 for Function Pointers in C
- Constructing grammar based on given rules
- Is this grammar LR(0) or SLR(1)
- ANTLR4 explain variable declaration error
- Bison ID reduction conflict
- SGF Grammar Parser with Peggy
Related Questions in CONTEXT-FREE-GRAMMAR
- Resolve shift/reduction conflict in grammar for expressions in PLY for calls to embedded functions
- Grammar for access to properties and calls to embedded functions
- Need clarification on pumping lemma for context free languages
- Java CUP produces Shift-Reduce conflict when parsing a grammar for a C++ type language
- Correct labeling for this regular language?
- How to recognize a context free grammar with a rust declarative macro
- Maximum recursion depth exceeded with nltk recursive descent parser
- Constructing grammar based on given rules
- how to find the grammar of this Language?
- ANTLR4 - parse function-like structures in regular text
- Context Free Grammar for L= { a^n b^m c^m d^2n }, where n and m are >= 0
- Is this grammar LALR(1)?
- How can I generate a Context Free Grammar for a specific language
- How to auto-complete JSON syntax strings?
- I have a problem in reducing a grammar to LL(1)
Related Questions in TURING-MACHINES
- Understanding Unary PCP Reduction to a Matching Problem (UPCP)
- Build a Turing Machine that counts a's and b's
- Language for Turing Machine
- Unable to export Chains class from Julia's Turing library
- Complicated, long equations in MCMC [Julia, Turing.jl]
- Turing Pattern Formation
- Is there a way to prove that the intersection of a decidable language and a recognizable language is also recognizable?
- binary search with JFLAP turing machine
- python - 3 Turing Machine script, getting errors on an undefined variable, even though I assigned it
- Prove that the following problem is undecidable by a reduction from the halting problem:
- Construct a Turing Machine that halts on an unbroken string of 1s
- Jump to a specific vector place if a condition is met and start reading it from there
- Binary to unary turing machine
- How to generate an Unrestricted grammar if a language defination is given
- Can we assure a strictly decreasing function is computable?
Related Questions in TURING-COMPLETE
- What is the most basic assembler language that is turing complete?
- Understanding the primitives which Turing showed to be sufficient for a programming language
- How would a Turing machine implement memory protection, interrupts, or real timer that a modern CPU has?
- Fixpoint of type exponentiation as a language
- Can any additional axiom make Coq Turing complete?
- TOC program A that when given any program B as input can determine whether or not B produces “hello world”
- Would x86 still be fully programmable if it didn't have the Sign Flag (SF)?
- Could you mine cryptocurrencies with the LaTeX language?
- Is pure Prolog Turing-complete, and if so, why can't it implement list intersection?
- Why is mov turing complete?
- Turing Machine For balanced parenthesis
- Datalog computational class?
- Turing machine for addition and comparison of binary numbers
- Is MapReduce Turing Complete?
- Is Move a Turing-complete language?
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular # Hahtags
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
We are often imprecise with these terms, but a correct answer to your question requires that we be very precise with how we are using terms.
Two computation systems are equivalent if they can simulate each other. A computation system is Turing-equivalent if it is equivalent to Turing machines.
A computation is complete with respect to a computation system if it requires all capabilities of that system to be computed in that system; that is, any change to the computing system which causes it not to be capable of performing at least the same computations as before will cause it not to be able to perform this computation. A computation is Turing-complete if it is complete with respect to Turing machines.
BNF grammars describe context-free languages, and the least capable computing system capable of parsing such languages are the pushdown automata. This computing system cannot simulate Turing machines in that there are computations a Turing machine can perform which a pushdown automaton cannot; therefore, pushdown automata are not Turing-equivalent.
The article says that TeX is a Turing-complete language, that is, deciding the language of valid TeX strings requires all capabilities of Turing machines. Any system not capable of simulating a Turing machine cannot possibly parse decide membership in the language of valid TeX strings.
The article is NOT saying that TeX is Turing-equivalent (maybe it is, maybe it isn't; I have no idea). As pointed out in the comment, Turing-completeness of a computation system's representation is completely unrelated to that computation system's Turing-equivalence. Even Turing machines themselves can be represented using strings of a regular language (in fact, extend the interpretation of any language so that otherwise invalid programs compile to the program which halts without doing anything, and suddenly ALL strings are valid, and the language of all strings is certainly regular).