Primitive Recursive Functions for a Working Programmer
The article discusses Turing completeness in programming languages, arguing that non-Turing complete languages can effectively solve practical problems. It explores theoretical implications, Turing machines, and finite state automata, emphasizing computational equivalence.
Read original article
discussions around the concept of Turing completeness in programming languages, often misinterpreted in practical contexts. The author argues that the lack of Turing completeness does not inherently limit a language's utility for solving practical problems. A key point made is that if a program in a Turing complete language runs faster than O(2^(2^N)), it can be implemented in a non-Turing complete language, suggesting that many practical problems do not require the full power of Turing machines. The article is structured into three parts: the first summarizes the theoretical implications of primitive recursive functions; the second provides an overview of Turing machines, finite state automata, and primitive recursive functions; and the third addresses practical applications. Finite state machines (FSMs) are introduced as simple recognizers that can only accept certain sets of strings, while Turing machines (TMs) are more complex, capable of performing computations with mutable tape. The author emphasizes that TMs do not execute user-supplied programs but operate based on a hard-wired transition function. However, it is possible to create a universal Turing machine that can simulate other TMs, leading to the Church-Turing thesis, which posits that TMs can represent any computation that can be performed algorithmically. The discussion highlights the equivalence of TMs and programming languages like Python in terms of computational power, underscoring the theoretical foundations of computation in programming.
Related
Rosser's Theorem via Turing Machines (2011)
The post delves into Rosser's Theorem, a potent extension of Gödel's Incompleteness Theorems, showcasing self-reference in formal systems. It elucidates Rosser's stronger disproof concept and its impact on system consistency. Additionally, it links Rosser's Theorem to the halting problem's unsolvability, underlining computational insights and Gödel's lasting influence on computability theory.
With fifth busy beaver, researchers approach computation's limits
Researchers led by graduate student Tristan Stérin determined BB(5) as 47,176,870 using Coq software. Busy beavers, introduced by Tibor Radó, explore Turing machines' behavior. Allen Brady's program efficiently analyzes and classifies machines, advancing computational understanding.
The Zombie Misconception of Theoretical Computer Science
The blog post delves into misconceptions in theoretical computer science, focusing on computability and complexity theory. It clarifies the distinction between functions and questions, NP-hard problems, and the P versus NP dilemma. Emphasizing the importance of grasping fundamental principles, the author seeks reader input on combating these misunderstandings.
Turing's topological proof that every written alphabet is finite (2010)
Alan Turing's 1936 article introduced the Turing machine and proved the undecidability of the halting problem, foundational in computer science. Turing's topological proof demonstrates limitations on symbol diversity in written languages and visual representations.
Is C99 actually Turing-complete? (2016)
The discussion examines whether C99 is Turing-complete, highlighting its memory limitations and practical constraints that prevent it from fully emulating a Turing machine in real-world scenarios.
10 comments~~While probably meant to simply, this statement sort-of undermines the author's credibility. I mean the "a very large number" part. Correct me if I'm wrong, but surly he means "a very fast growing function".~~
Or - it seems he mean the the program completes in less than O(2^(2^N)) steps.
Isn’t the advantage that an upper bound on the number of steps required can be computed statically?
This means we can refuse to compute things that violate some limit and give back a meaningful error, for all possible inputs.
Whereas with the Turing complete plus Runtime Limit approach, we might pick a limit that is too low for some inputs we care about. We won’t know until we run the computation and hit the limit! We see this sometimes with C++ template recursion.
I might be totally confused here so I hope some more knowledgable can weigh in :)
I agree with the author with regards to the stronger semantics, and that's why I thought of this language. You often want to have some guarantees over the execution time of your program. It would probably be PRF based at the core, but Turing complete in practice. Like how rust rejects invalid borrows but still offers unsafe for raw pointers, this lang would either calculate the upper bound based on the simple loop primitives, or you'd have to use the unsafe operators and provide an alternative formula for the bounds.
Also: s/necessary/necessarily/
> Typically, not being Turing-complete is extolled as a virtue or even a requirement in specific domains. I claim that most such discussions are misinformed — that not being Turing complete doesn’t actually mean what folks want it to mean
Why are those discussion misinformed? Most formal analysis tools (Coq, Isabelle, Agda(?)) usually require a proof that a function terminates. This is I think is equivalent to proving that it is total implying it is primitive recursive?
Related
Rosser's Theorem via Turing Machines (2011)
The post delves into Rosser's Theorem, a potent extension of Gödel's Incompleteness Theorems, showcasing self-reference in formal systems. It elucidates Rosser's stronger disproof concept and its impact on system consistency. Additionally, it links Rosser's Theorem to the halting problem's unsolvability, underlining computational insights and Gödel's lasting influence on computability theory.
With fifth busy beaver, researchers approach computation's limits
Researchers led by graduate student Tristan Stérin determined BB(5) as 47,176,870 using Coq software. Busy beavers, introduced by Tibor Radó, explore Turing machines' behavior. Allen Brady's program efficiently analyzes and classifies machines, advancing computational understanding.
The Zombie Misconception of Theoretical Computer Science
The blog post delves into misconceptions in theoretical computer science, focusing on computability and complexity theory. It clarifies the distinction between functions and questions, NP-hard problems, and the P versus NP dilemma. Emphasizing the importance of grasping fundamental principles, the author seeks reader input on combating these misunderstandings.
Turing's topological proof that every written alphabet is finite (2010)
Alan Turing's 1936 article introduced the Turing machine and proved the undecidability of the halting problem, foundational in computer science. Turing's topological proof demonstrates limitations on symbol diversity in written languages and visual representations.
Is C99 actually Turing-complete? (2016)
The discussion examines whether C99 is Turing-complete, highlighting its memory limitations and practical constraints that prevent it from fully emulating a Turing machine in real-world scenarios.