Questions tagged [turing-completeness]
The turing-completeness tag has no usage guidance.
196
questions
-2
votes
1
answer
85
views
Is DNA computation Turing complete?
I have heard DNA being referred to as "code", this is because it is an instruction set which dictates the bodies' properties. However, DNA (as far as I have learned), has no conditional ...
0
votes
0
answers
59
views
If a Turing machine can compute any computable problem how can Turing completeness be achived?
To my knowledge a Turing machine is able to compute anything considered computable.
I got the definition of Turing completeness from this answer Explain the difference between Turing Complete and ...
0
votes
0
answers
37
views
Is Brainf*ck still Turing Complete without I/O?
I've made an interetsing esolang, and to prove Turing completeness, I've written a small Brainf*ck interpreter in it. However, due to the nature of the language, input is rather hard to handle.
The ...
1
vote
1
answer
64
views
Why is the Church-Turing thesis not accepted as fact?
I recognize that it has overwhelming consensus at this point, but from what I understand, it's still technically considered "probably true" instead of "definitely true".
If we go ...
- 284
0
votes
2
answers
43
views
Why is Rule 110 considered "weakly" universal?
My supposition is that this is was more or less an automatic designation based on the fact that Rule 110 requires an infinite "background tiling" of the 14-bit sequence ...
- 284
1
vote
1
answer
44
views
Instances of simulating lambda calculus?
There are a ton of resources on the web devoted to proving some esoteric language is Turing complete by simulating arbitrary turing machines. I have an esoteric language I want to prove is complete, ...
- 225
1
vote
0
answers
101
views
The simplest Turing-complete language
To prove that a new language is Turing-complete the authors need to show that it can simulate any other (already known) Turing-complete language.
I wonder what Turing-complete language is the simplest ...
- 111
1
vote
0
answers
115
views
Simple proof that Lisp expresses all computable list functions
Given computable function $f : LispTerm \rightarrow LispTerm$ is it possible to implement it in Lisp?
The $LispTerm$ is any term that is constructed using cons, <...
- 93
0
votes
3
answers
106
views
Is Turing completeness necessary?
Most programming languages are Turing complete (finite memory blah blah blah), and when we design languages this is a goal.
But is it really necessary? What algorithms do we typically use that require ...
- 81
0
votes
1
answer
142
views
How does nondeterminism affect the power of a machine?
For example, in finite-state machines (FSM), the main difference between a deterministic (DFA) and a non-deterministic machine (NFA) is that there are possibly more branches or outputs for each input, ...
1
vote
1
answer
117
views
What exactly does Turing Equivalence mean?
Assume I have a programming language $L$ with well-defined semantics.
Showing Turing-completeness is straightforward: if I write a program using $L$ simulating the universal TM, I'm done.
What I'm ...
- 296
1
vote
0
answers
24
views
What are practical applications for markovs algorithm(string rewriting systems)
:)
Currently I am browsing through the internet on the hunt for a topic for my bachelors thesis. Whilst being on Reddit I discovered an interesting repo (https://github.com/mxgmn/MarkovJunior) for a ...
- 11
0
votes
0
answers
92
views
What is the most computationally efficient Turing complete system?
I'm making a program that involves making models of and working with arbitrary systems (or programs). What is the most computationally efficient Turing complete system to model these in?
By "...
0
votes
1
answer
68
views
What does it mean for a machine language to be Turing-complete?
I was reading the Wikipedia article on Turing completeness, but I was having a hard time putting together all of the concepts. In simple terms, what does it mean for an instruction set to have Turing-...
6
votes
2
answers
214
views
Do all Turing-complete programming languages have to contain infinite loops?
Intuitively, it seems that if a programming language is Turing-complete, then it must contain a program that's an infinite loop. I have formalized this below:
Conjecture. There does not exist a set $...
2
votes
1
answer
123
views
is HaltingFuck computable?
A while ago I defined the language HaltingFuck, but I've never been able to figure out its computational class. The language is defined as follows:
HaltingFuck is a language very much like Brainfuck, ...
- 375
1
vote
1
answer
44
views
Encoding Turing machine-like behavior using families of sequences of vector spaces and modules. P=NP related
Let $F$ be a field. Suppose we have a machine $T$ that works with words that are elements of $F$, for exmaple $F = \Bbb{Z}/2, \Bbb{Q}$ (using arbitrary precision arithmetic), or $\Bbb{Z}/p$ for a ...
2
votes
0
answers
76
views
Limited number of calling for a decision blackbox to compute all the solutions
I am trying to reduce between a solution problem and a decision version of the same problem.
The problem is the orthogonality problem. Given $2$ sets $L$ and $R$, whose size each is $n$ vectors over $\...
- 494
4
votes
1
answer
553
views
How could you encode such a function in lambda calculus?
I just read the definition of lambda calculus. Apparently it's Turing complete, but I tried writing a very simple function and I couldn't:
...
- 43
0
votes
1
answer
64
views
In a rigorous mathematical sense, what is the significance of Turing-completeness?
I know that Turing-completeness is the ability to simulate a Turing machine, and from what I've read, the reason why we should care about Turing-completeness is that it demonstrates that a machine can ...
- 1
1
vote
1
answer
90
views
kolmogorov complexity for finite Language?
In lectures my professor proved that there is no Turing machine that for every x it calculates k(x).
On the other hand, I saw a claim online that for finite language L there is a Turing machine that ...
- 61
0
votes
0
answers
45
views
Finite Number of Turing Machines that stop after k steps?
For this question suppose Alphabet for input is {0,1}.
Given:
L={<M> | M stops on every input after maximum 1000 steps}
My professor claimed that there is a ...
- 61
0
votes
0
answers
44
views
Is the set of all halting programs for all universal Turing machines recursively enumerable?
I understand that one can use dovetailing to recursively enumerate the domain of a UTM.
However, I am trying to recursively enumerate the domain of all possible UTM.
My starting point was to use a ...
- 345
5
votes
3
answers
3k
views
How Turing Machine Can Never Stop?
My professor discussed the following Turing machine M' on input (,x):
Generate number n
Run M on X, for n steps
If M stops, accept
I don't understand No.3
If we are running M on input X for final ...
- 61
0
votes
3
answers
186
views
Are all Turing machines Turing complete?
I have recently been reading up on TOC, and had this thought, which does not seem to be answered explicitly anywhere.
They way I have understood it, a system is Turing complete if it can simulate any ...
- 1
12
votes
8
answers
2k
views
Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?
I wish there were more, but the subject pretty much captures my whole question.
Is there a non-Turing-complete model (some constrained term rewriting system or automaton or what have you) which is ...
- 284
-1
votes
2
answers
51
views
Are there infinitely many distinct implementations of any algorithm using any Turing-complete computational model?
Subject pretty much says it all. My strong impression is that for any algorithm and any choice of programming language or computational model, if it's Turing-complete, then there must be infinitely ...
- 284
11
votes
2
answers
2k
views
Is Desmos Turing-Complete?
The graphing calculator Desmos has a ton of functions, and can express any arithmetric formula. What I want to know is, is it Turing-Complete?
Desmos supports, among other things:
Most mathematical ...
- 213
1
vote
1
answer
175
views
Had Conway's Game of Life or any C-A been demonstrated to generate non-repeating pattern?
As we know, Conway's Game of Life is Turing-complete. And Turing-complete systems can be used to calculate irrational numbers such as $\sqrt{2}$, $\pi$, $e$, etc. which have non-repeating digits.
So ...
- 161
4
votes
0
answers
96
views
Necessity of encoding for certain models of computation
Consider the following model of computation (from here).
Although Fractran is Turing-complete, it assumes that the "user" is able to perform the steps of encoding the input ($2^{n + 1}$) ...
- 91
-1
votes
1
answer
97
views
how can turing machines be universal models of computation if they can't perform binary search?
I have searched around and it seems like it is impossible for a Turing machine to implement binary search for an arbitrary sized array. How can a turing machine be called universally computable if it ...
- 23
2
votes
2
answers
143
views
How do we define the term "computation" across models of computation?
How do we define the term computation / computable function generically across models of computation?
Beginning with the textbook definitions of: {Linz, Sipser and Kozen} for "computable function&...
- 91
0
votes
1
answer
495
views
EQ_{TM} is not Turing recognizable, but we can reduce A_{TM} to it?
So as I understand $EQ_{TM}$ (problem of deceiding whether two turing machines are equivalent) is not Turing Recognizable (by showing that $A_{TM}$ is reducible to its complement ${NEQ_{TM}}$). But we ...
- 219
5
votes
1
answer
665
views
Explain the difference between Turing Complete and Turing Equivalence
I'm not sure if I understand the difference between Turing Complete and Turing Equivalent programming languages.
A computational system that can compute every Turing-computable
function is called ...
- 453
2
votes
0
answers
236
views
Is the While programming language with bounded number of variables Turing complete?
In our lecture it was proven that WHILE-Programs are turing-complete. In short a WHILE-Program only allows the following:
...
- 21
2
votes
1
answer
71
views
Computation equivalence of functional and procedural programming
I'm really interested in the idea of functional programming, it seems like a very modular way of doings things. I've seen some suggestion that functional programming is just as powerful as procedural ...
- 23
18
votes
2
answers
6k
views
Paradox? Pure Prolog is Turing-complete and yet incapable of expressing list intersection?
Pure Prolog (Prolog limited to Horn clauses only) is Turing-complete. In fact, a single Horn clause is enough for Turing-completeness.
However, pure Prolog is incapable of expressing list intersection....
- 465
1
vote
1
answer
185
views
What is the theoretical minimum number of "switches" requried to implement a Turing-complete CPU?
Where "switches" are the basic abstract building blocks for logic gates: vacuum tubes, transistors, magnetic relays, or whatever. We're not counting any switches in the RAM or tape drive ...
- 111
6
votes
2
answers
713
views
Can a total programming language be Turing-complete?
I've seen two answers to this:
Wikipedia says no:
These restrictions mean that total functional programming is not Turing-complete.
And the Wikipedia article cites D.A. Turner as the coiner of "...
- 316
0
votes
1
answer
60
views
Is there a #$P$-complete counting problem such that every (valid) instance of its decision version is a Yes-instance?
I want to know whether there is a decision problem, written EasyProblem, satisfying the follow property:
For every valid instance $x$, $x$ is a Yes-instance for EasyProblem (if we construct ...
- 613
0
votes
1
answer
56
views
What is the computational class of a pushdown automaton with real values?
Say there is a push-down automata, in this example I'll use a deadfish-like set:
+: increase x by 1
0: set x to 0
...
- 11
0
votes
1
answer
220
views
Universal Turing Machine algorithm
First, I learned this based on these facts:
Turing machine (TM) will be define with 7-tuple Notation, $M=\langle Q,G,b,S,d,q_0,F\rangle$.
Any computation rules that can use to simulate any possible ...
1
vote
2
answers
224
views
Is there a query language variant of Turing Completeness?
By this I mean a theory where you can say Language X is Query Complete so that you know that language is able to do any sort of query? I'm guessing not because some queries would run into things that ...
- 111
3
votes
2
answers
152
views
Intuition for Church-Turing thesis for Turing machines
I can very clearly see "why" mu-recursion is a universal model of computation, i.e. why the Church-Turing thesis -- that any physically computable algorithm can be executed with mu-recursion ...
0
votes
3
answers
1k
views
Is English Turing-complete?
Is English Turing-complete?
Intuitively it makes sense that English is Turing complete, since you can talk someone through building a Turing machine. But I also think there might be some operators ...
- 35
0
votes
1
answer
80
views
Why is the Halting problem decidable for Goto languages limited on the highest value of constants and variables?
This is taken from an old exam of my university that I am using to prepare myself for the coming exam:
Given is a language $\text{Goto}_{17}^c \subseteq \text{Goto}$. This language contains exactly ...
0
votes
1
answer
124
views
Turing-completeness of Goto language with limited constants
This is taken from an old exam of my university that I am using to prepare myself for the coming exam:
Given is a language $\text{Goto}_{17} \subseteq \text{Goto}$. This language includes exactly ...
-1
votes
1
answer
24
views
Determine if the following problem is decidable or not : Does the read–write head of a TM with the input w leave the word w?
Determine if the following problem is decidable or not : Does the read–write head of a TM with the given input w leave the word w on the tape?
- 147
-1
votes
1
answer
18
views
Is the Languague which contains all TMs which write the blank symbol at firs by the given input w decidable?
Consider the problem of determining whether a Turing machine M on an input w writes the blank symbol at first. Is this decidable ?
- 147
2
votes
1
answer
122
views
Confusion in Turings proof of the undecidability of the Entscheidungsproblem
I was reading Turing's paper on computable numbers and the Entscheidungsproblem. There is this part of Section 9, Part II that I cannot quite seem to understand. He says:
It is pretty straight ...
- 125