Questions tagged [turing-completeness]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
157 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. ...
-3
votes
3answers
145 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 ...
1
vote
0answers
17 views

Is there a recursive problem encoding the Turing completeness of a model of computation?

Suppose we have a model of computation $C$ we want to show to be Turing complete. The usual strategy would be to emulate within $C$ any model of computation we already know to be Turing complete (e.g. ...
-1
votes
2answers
145 views

To what extent is an x86 machine equivalent to a Turing Machine?

To what extent is an x86 machine equivalent to a Turing Machine? When I wrote this question I intended that the answer would be some named set of computations that a Turing machine could perform and ...
41
votes
9answers
12k 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 ...
0
votes
0answers
35 views

Is there defined limits on, how a Turing Machine can emulate itself / another one?

Meaning for example lower or upper bounds of any kind, possibly concerning time or space complexity?
2
votes
2answers
444 views

Explanation for indirect addressing

While reading about minimal instruction set computer I found out that one needs at least (for example) the ability to increment or decrement the value stored in register, a test for zero and a jump. ...
56
votes
6answers
13k views

Are there minimum criteria for a programming language being Turing complete?

Does there exist a set of programming language constructs in a programming language in order for it to be considered Turing Complete? From what I can tell from wikipedia, the language needs to ...
0
votes
1answer
60 views

How can Turing complete machines exist theoretically if the halting problem is undecidable

As the question says, if I input on the tape of a Turing complete machine a program that solves the halting problem with the correct inputs the program will never end its execution regardless of ...
5
votes
1answer
289 views

How to write a coterminating, effectful program?

[Using Idris for code examples and terminology, but the question is not about Idris per se] In a post titled A Neighborhood of Infinity, @sigfpe argues that "the kind of open-ended loop we see in ...
3
votes
2answers
150 views

What can't you do without Turing-completeness?

I suppose that, since a Turing-complete language can simulate a Turing-machine, a non-Turing-complete language can't, but most programs do not have the simulation of a Turing machine as their purpose. ...
0
votes
1answer
44 views

Number of logic gates for “reasonable” Turing completeness

Somewhere on stackexchage, I, or someone else asked what was the proper term for Turing completeness minus the infinite memory (e.g. a Turing machine that one can actually build, no bigger than your ...
0
votes
0answers
33 views

Is the language “untyped arithmetic expressions” in Types and Programming Languages not Turing complete?

In Types and Programming Languages by Pierce, is it correct that the language introduced in Chapter 3 Untyped Arithmetic Expressions is not Turing complete? Because it doesn't provide recursion. the ...
3
votes
1answer
161 views

Are fixed-point combinators general recursive?

I don't know if I'm using the vocabulary correctly, but what I'm interested in is this: If your language has fixed-point combinators, is it Turing-complete?
0
votes
0answers
33 views

I've proven my language undecidable what is left to prove it Turing equivalent?

Let us say that I have a computation model $A$. Let us also say that I have shown that $A$ can be simulated by a Turing machine. I have not been able to prove that $A$ can simulate a Turing machine. ...
-1
votes
1answer
126 views

Is the infinite program Turing-recognizable/decidable?

Imagine we have a program which does an infinite loop: while(true){loop} We run the program on a linux machine(assume the compilation is ok), then this linux ...
-1
votes
1answer
61 views

If the human brain is a Turing machine then how is it able to ascertain that certain problems are undecidable? [closed]

I recently read about the idea that the human brain might be a Turing machine (or Turing complete). If that is true then how is the brain able to reason that a certain problem is undecidable for e.g. ...
1
vote
2answers
106 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 ...
0
votes
1answer
70 views

Prove completeness of a language with Turing Machine

I'm trying to prove that a simple computer language is Turing Complete. For that, I did some researches about Turing Machine and I found (if I understand correctly), that we can prove that by simuling ...
5
votes
4answers
2k views

Are Finite Automata Turing Complete?

Something is Turing Complete if it can be used to simulate any Turing Machine. So, can a Finite Automaton simulate a Turing Machine? On the question Can regular languages be Turing complete? they ...
0
votes
2answers
50 views

Are Linear Bounded Automatons Turing Complete?

Linear Bounded Automatons are just Turing Machines with finite tape, instead of infinite tape. But this causes them to not be Turing Complete? Why?
0
votes
1answer
66 views

What are the benefits of languages that are not Turing complete?

Unfortunately I did a degree in CS without much theoretical computer science. One thing I used to hear is that sub languages, or languages which are not Turing complete, allow for better optimization? ...
3
votes
1answer
44 views

Uncomputably coded model of computation

There are many different but equivalent models of computation. I assume their equivalence is shown by coding input of one model to the input of the other model and making an argument why should there ...
32
votes
5answers
6k views

Can regular languages be Turing complete?

I was reading about Iota and Jot and found this section confusing: Unlike Iota, where the syntactic tree for a string can branch either on the left or on the right, Jot syntax is uniformly left-...
0
votes
2answers
132 views

Are Context Sensitive Languages Turing Complete? [duplicate]

Related questions: Can regular languages be Turing complete? Why are Linearly Bounded Turing Machines more powerful than Finite State Automata? https://stackoverflow.com/questions/14589346/is-c-...
1
vote
2answers
75 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 ...
1
vote
2answers
65 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
56 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
4k 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
215 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 ...
6
votes
0answers
33 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. ...
1
vote
0answers
98 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
84 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
86 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
50 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 ...
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
81 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
204 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
179 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
172 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
57 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
117 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 ...
22
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
232 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 ...
3
votes
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
37 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
89 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 ...
26
votes
7answers
7k 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
42 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$ ...