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.)
223 questions
7
votes
1
answer
275
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
113
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, ...
- 141
0
votes
0
answers
40
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 ...
- 213
1
vote
0
answers
53
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
70
views
Equivalence of Infinite Turing Machines
Given a Turing machine M, is it true that there exist infinitely many Turing machines equivalent to it?
0
votes
0
answers
31
views
How to define a normal Markov algorithm (NMA) to swap two ternary numbers separated by the symbol "^"?
I'm trying to write a normal Markov algorithm in an emulator to swap two ternary numbers separated by the symbol "^". For example, for input "120^210", the result should be "...
1
vote
0
answers
43
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?
- 213
0
votes
1
answer
89
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
124
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
69
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
87
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
56
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
140
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 ...
0
votes
1
answer
100
views
Is it possible to use a non-Turing-complete language to describe the steps to build a Turing Machine?
First of all, it is impossible to use a Turing-incomplete language to simulate a Turing-complete one (see link)
However, is it possible to use a Turing-incomplete language to describe the steps to ...
- 111