Questions tagged [turing-completeness]
A language or system is Turing-complete if it can compute anything a Turing Machine can; one way to show this is by simulating a universal Turing machine. (Implementing lambda calculus also works.)
224 questions
2
votes
0
answers
24
views
Does a UTM exist with this fixed binary “program#input → output” tape convention? (reference)
I’m wondering whether a universal Turing machine can exist with a very simple fixed alphabet and I/O + program convention, as follows.
Machine model
$\Sigma=\{0,1\}$
$\Gamma=\{0,1,B,\#\}$
single one-...
1
vote
0
answers
65
views
Is "Tiny Tag" Turing-Complete?
I have recently been investigating Turing-Complete systems and discovered something called “Cyclic Tag”. It is relatively simple to explain, it involves transforming an initial binary string through ...
- 11
7
votes
1
answer
315
views
What are the fundamental arguments for the correctness of the Church-Turing thesis?
I'm interested in gathering some solid arguments in favor of the Church-Turing thesis, which states that anything computable by an algorithm can be computed by a Turing machine. I understand that ...
- 207
2
votes
0
answers
131
views
is there a concept of 'proof-completeness' equivalent to turing completeness
This question comes from curry-howard correspondence.
I am a beginner in this particular topic, i dont yet have much knowledge in proof theory or formal logic or type theory. But as i observed here, ...
- 157
0
votes
0
answers
47
views
Properties of the sequence and its generators listing Gödel numbers of programs with a particular syntactic property
Given a Gödel numbering of programs in a Turing complete language, consider a sequence of the Gödel numbers of programs that have a particular syntactic property (or more generally, non-(non-trivial ...
- 203
1
vote
0
answers
61
views
Defining an algorithm via Gödel numbers
Gödel managed to sneak self-reference into Principia Mathematica (PM). He showed that PM—and all other sufficiently expressive formal systems—contain unsolvable problems (aka unprovable theorems).
...
- 211
3
votes
1
answer
1k
views
Universality all the way down?
Universality is the ability of a machine to compute any other machine. So, in particular, a universal machine (UM) can also compute another UM.
Now, practically, a universal Turing machine (UTM) must ...
- 211
0
votes
1
answer
79
views
Equivalence of Infinite Turing Machines
Given a Turing machine M, is it true that there exist infinitely many Turing machines equivalent to it?
5
votes
0
answers
102
views
Probability that random turing machine program is universal?
What is the probability that a random n-symbol, m-state Turing Machine program is a Universal Turing Machine?
Does a Chaitin's constant equivalent for this question exist?
- 203
0
votes
1
answer
95
views
If a system can non-trivially write a self-interpreter, is it necessarily Turing complete?
We've all seen the brainf*ck interpreter written in brainf*ck, or the game of life running in the game of life.
Does the ability for a language/program/system to stimulate itself necessarily make it ...
- 113
0
votes
1
answer
151
views
How can we test for Turing Completeness given any formal semantic specification?
I have seen the question asked many times always with the same answer: emulate a Turing machine on top of it. This seems like an ad hoc method so is there a more formal and general method to prove ...
1
vote
1
answer
77
views
Logarithmic space reduction from PATH to 2COLOR-PATH
2COLOR-PATH = {<G,s,t> | G is a 2-Colorable directed graph that has a directed path from s to t}
I need to write a logarithmic space reduction from PATH to 2COLOR-PATH (explained above). I know ...
- 141
3
votes
0
answers
98
views
2-argument combinators and Turing completeness
SK, BCKW, and BAMT combinator systems are known to be Turing-complete and convertible into each other. (BAMT is mentioned in this blog post)
...
- 498
0
votes
0
answers
59
views
How simple addition operation performed with just one instruction by BitBitJump?
According this:
https://en.m.wikipedia.org/wiki/One-instruction_set_computer
Its instruction has 3 operands, the meaning is: copy the bit addressed by a to the bit addressed by b and jump to the ...
1
vote
1
answer
210
views
What are the most minimalistic assembly's mnemonics to make complete turing machine?
Disclaimer: I'm a computer engineering student, not a computer science. Pardon me for mistakenly using computer science terms.
I want to design computer architecture with the most minimalist design as ...