Questions tagged [turing-completeness]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
2answers
113 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 ...
3
votes
2answers
38 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
3answers
191 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 ...
0
votes
1answer
41 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
1answer
37 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
1answer
20 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?
-1
votes
1answer
13 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 ?
2
votes
1answer
79 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 ...
0
votes
2answers
20 views

Equivalence between a TM and a changing TM

Let a changing TM be a TM which is not able to write the same symbol which is being read. Formal: $M^*=(Q,\Sigma,\Gamma,\delta,q_{accept},q_{reject})$,$\delta(q,a)=(q^*,a^*,c),a \neq a^*$ with $q,q^...
2
votes
1answer
38 views

Lambda calculus without free variables is as strong as lambda calculus?

First question: How would one prove that by removing free (unbound) variables from lambda calculus, and allowing only bound variables, its power is not reduced (it is still Turing-complete) ? Second ...
1
vote
1answer
43 views

Turing machine that can move right only $O(1)$ steps beyond input

I need to prove that a Turing machine that can move only $k$ steps on the tape after the last latter of the input word is not equal to a normal Turning machine. My idea is that given a finite input ...
1
vote
0answers
40 views

If a turing machine can't solve the halting problem for a machine X, does this imply that X is at least as powerful as a turing machine?

Say I have a deterministic machine X, and I prove that a turing machine can't solve the halting problem for this machine when given a certain input. Does this imply that this machine X is turing-...
1
vote
0answers
34 views

Turing-completeness of affine programs

Are unguarded affine programs Turing-Complete? Are affine programs with affine guards Turing-Complete? Unguarded program: all branches are taken Affine program: only assignments like $x:=x_1+5x_2-...
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
245 views

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

Is this statement true? Any computation that is decidable within the "C" programming language or the x86 machine language would be decidable on an actual Turing Machine on the basis of the ...
0
votes
0answers
36 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?
0
votes
1answer
65 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
294 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
193 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
0answers
38 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 ...
0
votes
1answer
54 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
34 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
151 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
65 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. ...
0
votes
1answer
73 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 ...
6
votes
4answers
3k 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
64 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
77 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
45 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 ...
0
votes
2answers
178 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
85 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
68 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
80 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 ...
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
83 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
1answer
315 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 ...
1
vote
0answers
120 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
87 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
95 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
52 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 ...
-2
votes
3answers
208 views

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

Does undecidability violate Turing completeness? Shouldn't "complete" include "decidability"? The halting problem: The halting problem is a decision problem about properties of computer programs ...
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
93 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
2answers
66 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 ...
2
votes
2answers
186 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 ...
0
votes
1answer
146 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 ...
1
vote
1answer
163 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. ...
5
votes
0answers
245 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
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
90 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 ...