Questions tagged [turing-completeness]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4
votes
1answer
512 views

How could you encode such a function in lambda calculus?

I just read the definition of lambda calculus. Apparently it's Turing complete, but I tried writing a very simple function and I couldn't: ...
0
votes
1answer
43 views

In a rigorous mathematical sense, what is the significance of Turing-completeness?

I know that Turing-completeness is the ability to simulate a Turing machine, and from what I've read, the reason why we should care about Turing-completeness is that it demonstrates that a machine can ...
0
votes
1answer
34 views

kolmogorov complexity for finite Language?

In lectures my professor proved that there is no Turing machine that for every x it calculates k(x). On the other hand, I saw a claim online that for finite language L there is a Turing machine that ...
0
votes
0answers
39 views

Finite Number of Turing Machines that stop after k steps?

For this question suppose Alphabet for input is {0,1}. Given: L={<M> | M stops on every input after maximum 1000 steps} My professor claimed that there is a ...
0
votes
0answers
24 views

Is the set of all halting programs for all universal Turing machines recursively enumerable?

I understand that one can use dovetailing to recursively enumerate the domain of a UTM. However, I am trying to recursively enumerate the domain of all possible UTM. My starting point was to use a ...
5
votes
3answers
3k views

How Turing Machine Can Never Stop?

My professor discussed the following Turing machine M' on input (,x): Generate number n Run M on X, for n steps If M stops, accept I don't understand No.3 If we are running M on input X for final ...
0
votes
0answers
50 views

Are all Turing machines Turing complete?

I have recently been reading up on TOC, and had this thought, which does not seem to be answered explicitly anywhere. They way I have understood it, a system is Turing complete if it can simulate any ...
12
votes
8answers
2k views

Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?

I wish there were more, but the subject pretty much captures my whole question. Is there a non-Turing-complete model (some constrained term rewriting system or automaton or what have you) which is ...
0
votes
2answers
41 views

Are there infinitely many distinct implementations of any algorithm using any Turing-complete computational model?

Subject pretty much says it all. My strong impression is that for any algorithm and any choice of programming language or computational model, if it's Turing-complete, then there must be infinitely ...
6
votes
2answers
598 views

Is Desmos Turing-Complete?

The graphing calculator Desmos has a ton of functions, and can express any arithmetric formula. What I want to know is, is it Turing-Complete? Desmos supports, among other things: Most mathematical ...
1
vote
1answer
119 views

Had Conway's Game of Life or any C-A been demonstrated to generate non-repeating pattern?

As we know, Conway's Game of Life is Turing-complete. And Turing-complete systems can be used to calculate irrational numbers such as $\sqrt{2}$, $\pi$, $e$, etc. which have non-repeating digits. So ...
4
votes
0answers
90 views

Necessity of encoding for certain models of computation

Consider the following model of computation (from here). Although Fractran is Turing-complete, it assumes that the "user" is able to perform the steps of encoding the input ($2^{n + 1}$) ...
-1
votes
1answer
87 views

how can turing machines be universal models of computation if they can't perform binary search?

I have searched around and it seems like it is impossible for a Turing machine to implement binary search for an arbitrary sized array. How can a turing machine be called universally computable if it ...
2
votes
2answers
98 views

How do we define the term "computation" across models of computation?

How do we define the term computation / computable function generically across models of computation? Beginning with the textbook definitions of: {Linz, Sipser and Kozen} for "computable function&...
0
votes
1answer
127 views

EQ_{TM} is not Turing recognizable, but we can reduce A_{TM} to it?

So as I understand $EQ_{TM}$ (problem of deceiding whether two turing machines are equivalent) is not Turing Recognizable (by showing that $A_{TM}$ is reducible to its complement ${NEQ_{TM}}$). But we ...
5
votes
1answer
282 views

Explain the difference between Turing Complete and Turing Equivalence

I'm not sure if I understand the difference between Turing Complete and Turing Equivalent programming languages. A computational system that can compute every Turing-computable function is called ...
2
votes
0answers
208 views

Is the While programming language with bounded number of variables Turing complete?

In our lecture it was proven that WHILE-Programs are turing-complete. In short a WHILE-Program only allows the following: ...
2
votes
1answer
67 views

Computation equivalence of functional and procedural programming

I'm really interested in the idea of functional programming, it seems like a very modular way of doings things. I've seen some suggestion that functional programming is just as powerful as procedural ...
18
votes
2answers
5k views

Paradox? Pure Prolog is Turing-complete and yet incapable of expressing list intersection?

Pure Prolog (Prolog limited to Horn clauses only) is Turing-complete. In fact, a single Horn clause is enough for Turing-completeness. However, pure Prolog is incapable of expressing list intersection....
1
vote
1answer
98 views

What is the theoretical minimum number of "switches" requried to implement a Turing-complete CPU?

Where "switches" are the basic abstract building blocks for logic gates: vacuum tubes, transistors, magnetic relays, or whatever. We're not counting any switches in the RAM or tape drive ...
6
votes
1answer
543 views

Can a total programming language be Turing-complete?

I've seen two answers to this: Wikipedia says no: These restrictions mean that total functional programming is not Turing-complete. And the Wikipedia article cites D.A. Turner as the coiner of "...
0
votes
1answer
55 views

Is there a #$P$-complete counting problem such that every (valid) instance of its decision version is a Yes-instance?

I want to know whether there is a decision problem, written EasyProblem, satisfying the follow property: For every valid instance $x$, $x$ is a Yes-instance for EasyProblem (if we construct ...
0
votes
1answer
49 views

What is the computational class of a pushdown automaton with real values?

Say there is a push-down automata, in this example I'll use a deadfish-like set: +: increase x by 1 0: set x to 0 ...
0
votes
1answer
156 views

Universal Turing Machine algorithm

First, I learned this based on these facts: Turing machine (TM) will be define with 7-tuple Notation, $M=\langle Q,G,b,S,d,q_0,F\rangle$. Any computation rules that can use to simulate any possible ...
1
vote
2answers
159 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
89 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
734 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
62 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
80 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
23 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
15 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
93 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
25 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
96 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
89 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
85 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
38 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
20 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. ...
2
votes
4answers
615 views

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

To what extent is the abstract model of computation specified by the x86 language Turing complete? The above question is related to this question: Is C actually Turing-complete? In theoretical ...
0
votes
1answer
94 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
328 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 ...
4
votes
2answers
486 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
76 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
172 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
41 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
422 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
142 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
104 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
165 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?