Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [turing-completeness]

The tag has no usage guidance.

1
vote
1answer
41 views

Proving Turing Completeness by creating a compiler to a Turing Complete language

Given a programming language A unknown to be Turing Complete, if one can create a compiler for a TC programming language B using A does this imply that A is itself Turing Complete? If so, what is the ...
0
votes
2answers
50 views

Can a language with some set of higher-order functions like map, fold and filter but without recursion or iteration be Turing complete?

I was reading this article and was wondering if there is any finite set of higher-order functions like map, fold or filter such that they could empower a language to be Turing complete even without ...
1
vote
1answer
127 views

Can PDA model Turing Complete objects if the objects' state are finite?

I am currently reading the extended Version of the Paper Online Detection of Effectively Callback Free Objects with Applications of Smart Contract. I am trying to understand the proofs of Chapter 6. ...
1
vote
1answer
22 views

Is turing completeness related to recursive enumerable languages?

I recently came across this term "Turing complete" in my study of morphogenesis models. When I looked up, it said that a turing complete machine can simulate a universal turing machine. When I ...
15
votes
2answers
3k views

What makes PROLOG Turing-complete?

I know that it can be proven PROLOG is Turing-complete by constructing a program that simulates a Turing machine like this: ...
0
votes
1answer
91 views

Is arithmetic turing complete?

Maybe my question doesn't make sense, because I lack some more thorough understanding, but I was curious if arithmetic was Turing complete? As I understand it, a "model of computation" is a mechanism ...
38
votes
9answers
7k views

Is C actually Turing-complete?

I was trying to explain to someone that C is Turing-complete, and realized that I don't actually know if it is, indeed, technically Turing-complete. (C as in the abstract semantics, not as in an ...
1
vote
1answer
82 views

Transport Triggered CPU Architecture MOV and Turing Completeness

Reading up on TTA CPU designs and the wikipedia article states that Some TTA implementations support conditional execution. The trick to make an TTA ISA Turing-complete with an unconditional MOV ...
6
votes
0answers
27 views

Unbounded-time programs in lambda calculus?

The Turing machine model has been extended to “infinitary turing machines”, which are Turing machines that can perform a countably and uncountably infinite amount of computations in finite time. Is ...
0
votes
0answers
81 views

Is C actually turing complete follow up [duplicate]

I am picking up from this thread for which I have no privileges to comment on: Is C actually Turing-complete? I was wondering if there's any progress on this and what the conclusion actually was. ...
0
votes
0answers
43 views

Does a Turing complete set of invertible combinators exist?

We'll say that a combinator A is invertible if there exists A' s.t. A'(Ax) = A(A'x) = x For example, Sxyz = xz(yz) is clearly invertible in this sense because we ...
0
votes
0answers
34 views

If only using bit-shifts can produce a Turing-machine, or if you need more bitwise operations

So you can have One Instruction Set Computers. But typically these instructions have rather complicated underlying implementations. addition (addleq, add and branch if less than or equal to zero) ...
7
votes
0answers
77 views

Automata that is Turing complete if you add a nondeterminism

Pushdown automata have an interesting property: non-deterministic ones belong to a different computational class than deterministic ones. This is in contrast to finite state and turing machines, for ...
2
votes
1answer
53 views

Can one get Turing-completeness without nontermination?

As I'm reading the movfuscator paper by Stephen Dolan, I encounter this claim: In order to have Turing-completeness, we must allow for nontermination. This seems like a reasonable statement. But I'...
3
votes
0answers
40 views

Computability of Kolmogorov complexity in total languages

It is well known that the Kolmogorov complexity is uncomputable in Turing-complete programming languages. However, what about total programming languages? For example, is the Kolmogorov complexity of ...
-3
votes
3answers
96 views

Does undecidability violate Turing completeness? Shouldn't “complete” include “decidability”? [closed]

Does undecidability violate Turing completeness? Shouldn't "complete" include "decidability"? That is, if one has a language that's Turing complete, but expresses infinite computation (i.e. may not ...
12
votes
2answers
1k views

How many pairs of brackets are sufficient to make Brainfuck Turing complete?

Brainfuck is a Turing complete programming language that uses only 8 symbols (6 if you ignore I/O). The two most notable ones that push it to Turing completeness are ...
0
votes
2answers
50 views

Halting problem of TM which recognize recursive languages is undecidable?

I am preparing for an exam and I came across this question in one of the tests. Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False) The solution ...
3
votes
1answer
194 views

Is the system of measuring length in the US Turing complete?

The author here writes: Little known fact, the system of measuring length in the US is Turing complete My question is: Is the system of measuring length in the US Turing complete?
2
votes
2answers
72 views

Is this system Turing complete?

I want to develop a genetic program that can solve generic problems like surviving in a computer game. Since this is for fun/education I do not want to use existing libraries. I came up with the ...
1
vote
2answers
166 views

np-complete proof, turing reduction

I have some difficulties with a complexity proof : I work with 3 problems : A, B and C I know : A-> B A-> C C -> B A-> B meaning : if I have a "yes answer " for A , then I have a "yes answer" for B. ...
3
votes
2answers
50 views

Weaker, but similar conditions to Turing completeness?

A model of computation is called Turing complete if it can simulate any Turing machine. This rules out for example a combinational logic circuit. However, there is a sense in which combinational ...
0
votes
1answer
49 views

What is the simplest/smallest subset an OOP language like C#/JavaScript that is Turing-complete?

This question is not meant to be too theoretical or nitpicky. I have experience programming, so I'm trying to get a better understanding of what it takes to get Turing-completeness by using my ...
21
votes
1answer
1k views

Does a do-while loop suffice for Turing-completeness?

I know that, in imperative programming languages, a while-do loop is sufficient as a control flow construct to make the language Turing-complete (as far as control flow goes - of course we also need ...
5
votes
0answers
147 views

Why does Turing Tumble need gear bits to be turing complete?

I understand intuitively that gear bits in the massively successful Turing Tumble game (funded by kickstarter) are necessary for Turing completeness*. I had a fantasy about building a computer with ...
1
vote
3answers
1k views

How can a stack-based VM be Turing-Complete?

I was trying to implement a stack-based Virtual Machine (e.g. like JVM or some early version of Lua) for some benchmarks in order to test its performance against a Register-based VM. I originally ...
1
vote
1answer
30 views

Obtain all possible Turing Machines from a Universal Turing Machine

Knowing how a Universal Turing Machines works and its capabilities, is it possible to obtain the collection M = {M0 , M1 , M2 , M3, … } of all possible Turing Machines? If so, can we prove that a ...
0
votes
2answers
57 views

How can a 64KiB computer do the same task as a modern computer?

I took an extremely interesting intro to CE course, learning about transistors/memory/logic gates up to LC-3 assembly. Something that was really interesting to me was learning about how a processor's ...
25
votes
7answers
6k views

Are all turing complete languages interchangeable

Note, while I know how to program, I'm quite a beginner at CS theory. According to this answer Turing completeness is an abstract concept of computability. If a language is Turing complete, then ...
1
vote
1answer
40 views

How to compute (x MOD y) with just SUM and MULT gates?

It is known that $\{ SUM, MULT \}$ is Turing-complete, i.e. every Turing machine has an equivalent circuit made up of $SUM$ and $MULT$ gates. By the way, I could not come up with designing $MOD$ ...
0
votes
0answers
30 views

Is it possible to have a code which cannot be solved by computer

I was looking at Turing machines and Turing completeness and I was wondering whether it is possible to prove that there is a problem which cannot be solved by a Turing complete computer or whether it ...
1
vote
1answer
49 views

Emergent complexity and Turing Completeness

Is there some link between the concept of emergence and Turing Completeness? The ideas feel intuitively like they might be linked, but I can find nothing online. The idea came to me because I was ...
1
vote
0answers
46 views

In what sense can a cellular automaton be Turing complete? [duplicate]

The rule 110 cellular automaton is known (or claimed) to be Turing complete. But what exactly does it mean? I do know what Turing completeness mean. Roughly speaking a language is Turing complete if ...
2
votes
1answer
177 views

Infinite Boolean circuits as a model of computation

Boolean circuits are non-uniform models of computation in that they require a different circuit for each length of input. The typical way of uniformizing a family of Boolean circuits is to define a ...
6
votes
1answer
4k views

How is PowerPoint Turing complete?

From my understanding, Turing complete means that the program or machine can complete any computation that a Turing machine can complete, which to me means any computation. So how can something like ...
42
votes
9answers
14k views

Why are some programming languages Turing complete but lack some abilities of other languages?

I came across an odd problem when writing an interpreter that (should) hooks to external programs/functions: Functions in 'C' and 'C++' can't hook variadic functions, e.g. I can't make a function that ...
1
vote
1answer
481 views

What was the first Turing-Complete programming language?

What was the first turing-complete language? Know about the first machines and computers, but not the programming language.
10
votes
1answer
199 views

Is there a dual concept to “Turing Complete” in logic?

Two computing models can be shown to be co complete if each can encode a universal simulator for the other. Two logics can be shown to be co complete if an encoding of the rules of inferences (and ...
3
votes
1answer
139 views

Who was the first to show that there is a Universal Turing-Machine that uses a binary alphabet?

The title says it all, I think. We know there are universal Turing-machines that only use a binary alphabet. But who proved this first? Turing himself showed the existence of a universal Turing ...
1
vote
3answers
212 views

Is the ability to do depth first search a proof of Turing Completeness? Can we write a non-TC automaton that does DFS?

As the title states. Let's say we have a set of inputs that define a tree structure. Is it possible to construct an automaton that can perform depth-first search on this data that is not Turing-...
3
votes
1answer
824 views

Turing-completeness, Conway's Game of Life and Logical Gates

I was recently given an assignment at university asking me to discuss the universal computational capability of Conway's Game of Life. I'm not required to actually build up a Universal Turing machine ...
1
vote
1answer
91 views

Is there a problem solution which, if implementable in a given language, implies that that language is Turing complete?

I have been researching a bit lately and found myself thinking about the title question for some time now, but have found nothing conclusive. For example, some problems require loops practically - ...
1
vote
0answers
39 views

What portion of all possible turing machines halt?

Has anyone estimated Chaitin's constant for Turing machines with an empty tape as input?
5
votes
0answers
92 views

Is a reduced Wang B-machine Turing-complete?

A Wang B-machine has only 4 instructions: right: Move tape head right left: Move tape head left ...
0
votes
1answer
161 views

Find the odd shortest path is NL

OddPath be a set of all G, s, t, such that G is a directed graph with a path from node s to node t, and the shortest such path has odd number of edges. How can I show OddPath is NL? I think about it ...
5
votes
1answer
231 views

Lambda Calculus in Rewriting systems

How to do or implement Lambda Calculus in a Rewriting systems? Rewriting systems are Turing complete. But I can't figure out how to do lambda calculus or functions with them.
1
vote
1answer
181 views

How many gates until Turing Complete

A computer can be pretty much made using just nand gates and a clock. Suppose you randomly place down nand gates on a board and connect them randomly to other nand gates. How many gates does someone ...
12
votes
1answer
1k views

Is any language that can express its own compiler Turing-complete?

A comment over on tex.SE made me wonder. The statement is essentially: If I can write a compiler for language X in language X, then X is Turing-complete. In computability and formal languages ...
32
votes
5answers
12k views

What does being Turing complete mean?

I see that most definitions of what it is to be Turing-complete are tautological to a degree. For example if you Google "what does being Turing complete mean", you get: A computer is Turing ...
6
votes
2answers
674 views

Looping and branching with Algorithmic Differentiation

Algorithmic (aka Automatic) Differentiation is a wonderful technique for numerical computation of derivatives. I understand how it relates to the fact that we know how to deal with every elementary ...