Questions tagged [turing-completeness]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
3 answers
52 views

What is the name of the theory that says that Turing equivalence is universal, and Turing machines are maximally computationally powerful?

In the Chomsky hierarchy, level 0 grammars include all languages that can be recognized by a Turing machine. There is no level -1 (which would represent the class of languages that cannot be ...
Luke Hutchison's user avatar
4 votes
1 answer
101 views

Is the Turing machine the only framework to analyse limits of computation?

In Theory of Computation lessons, the limits of computation are usually analyzed within the framework of Turing machines, so if something isn't solvable with Turing Machine, then we consider this ...
math boy's user avatar
0 votes
0 answers
25 views

Effectively universal Turing machines and Turing-completeness?

An effectively universal Turing machine $T$ is a Turing machine for which there exists a recursive reduction $f$ such that $\forall A:U(A)=T(f(A))$, where $A, f(A)$ are finite sequences of symbols (...
rus9384's user avatar
  • 1,632
2 votes
2 answers
145 views

Prove that there aren't any complete languages

Prove that there isn't a complete language over a given alphabet $\Sigma$. That is, there is no $C \subseteq \Sigma^*$ such that every $L \subseteq \Sigma^*$ is Turing-reducible to $C$. Attempt: Let $...
NiStack's user avatar
  • 47
0 votes
3 answers
48 views

Does a language/maschine/system need to be able to halt to be universal?

Is it possible for a language (or machine or system) to be universal or turing complete, when there is no possibility to write a program for it that halts? Lets say we create a new language, brainfuck-...
12431234123412341234123's user avatar
1 vote
4 answers
3k views

Can we ever achieve Turing completeness?

I want to relate Turing completeness to the Halting Problem. As far as I know we say something is turing complete (eg: a programming language) when it can compute any function and can do any task. But ...
D Star Let's Explore's user avatar
2 votes
3 answers
310 views

Does the first incompleteness theorem imply that any Turing complete programming language must have undefined behavior?

If I understand correctly, the first incompleteness theorem says that any "effectively axiomatized" formal system which is consistent must contain theorems which are independent of the ...
Mikayla Eckel Cifrese's user avatar
2 votes
2 answers
137 views

What are quines (layman friendly)?

I was going through the Wikipedia page on Quines and did not understand this paragraph - A quine is a fixed point of an execution environment, when the execution environment is viewed as a function ...
DashwoodIce9's user avatar
3 votes
1 answer
2k views

Is a machine Turing-complete when it can decide a context-sensitive language?

If a machine can decide a context-sensitive language (like the language of palindromes with a non-linear center) is that fact a proof that the machine is Turing-complete? Can this be used to prove ...
Barney's user avatar
  • 155
17 votes
3 answers
4k views

Does the Turing test have anything to do with Turing completeness or Turing machines?

I am studying Turing machines and Turing completeness and just remembered I saw something called the Turing test. It seems that the Turing test (from Wikipedia) is a test of a machine's ability to ...
Hang Chen's user avatar
  • 335
1 vote
1 answer
35 views

Concrete example of a set with a lower degree of unsolvability

Post's problem, posed in 1944 by Post, was to know if there is a recursively enumerable set, which, being undecidable, was not equivalent to the Halting problem under Turing reducibility. While I've ...
user6767509's user avatar
0 votes
0 answers
53 views

Why, in principle, can a Turing machine describe any computation or procedure?

Why is it that a Turing machine can perform all kinds of calculations and procedures? As a test, I tried to perform a four-quadratic calculation using a Turing machine myself. However, although I ...
yt10's user avatar
  • 1
-2 votes
1 answer
415 views

Is DNA computation Turing complete?

I have heard DNA being referred to as "code", this is because it is an instruction set which dictates the bodies' properties. However, DNA (as far as I have learned), has no conditional ...
a_verry_long_variable_name's user avatar
0 votes
0 answers
66 views

If a Turing machine can compute any computable problem how can Turing completeness be achived?

To my knowledge a Turing machine is able to compute anything considered computable. I got the definition of Turing completeness from this answer Explain the difference between Turing Complete and ...
Alessandro Tornesi's user avatar
1 vote
1 answer
99 views

Why is the Church-Turing thesis not accepted as fact?

I recognize that it has overwhelming consensus at this point, but from what I understand, it's still technically considered "probably true" instead of "definitely true". If we go ...
Trev's user avatar
  • 296
0 votes
2 answers
93 views

Why is Rule 110 considered "weakly" universal?

My supposition is that this is was more or less an automatic designation based on the fact that Rule 110 requires an infinite "background tiling" of the 14-bit sequence ...
Trev's user avatar
  • 296
1 vote
1 answer
56 views

Instances of simulating lambda calculus?

There are a ton of resources on the web devoted to proving some esoteric language is Turing complete by simulating arbitrary turing machines. I have an esoteric language I want to prove is complete, ...
lightning's user avatar
  • 225
1 vote
0 answers
138 views

The simplest Turing-complete language

To prove that a new language is Turing-complete the authors need to show that it can simulate any other (already known) Turing-complete language. I wonder what Turing-complete language is the simplest ...
Danylo Y's user avatar
  • 111
1 vote
0 answers
121 views

Simple proof that Lisp expresses all computable list functions

Given computable function $f : LispTerm \rightarrow LispTerm$ is it possible to implement it in Lisp? The $LispTerm$ is any term that is constructed using cons, <...
prog's user avatar
  • 93
0 votes
3 answers
150 views

Is Turing completeness necessary?

Most programming languages are Turing complete (finite memory blah blah blah), and when we design languages this is a goal. But is it really necessary? What algorithms do we typically use that require ...
StackMachine's user avatar
0 votes
1 answer
250 views

How does nondeterminism affect the power of a machine?

For example, in finite-state machines (FSM), the main difference between a deterministic (DFA) and a non-deterministic machine (NFA) is that there are possibly more branches or outputs for each input, ...
learningturingmachines's user avatar
2 votes
1 answer
175 views

What exactly does Turing Equivalence mean?

Assume I have a programming language $L$ with well-defined semantics. Showing Turing-completeness is straightforward: if I write a program using $L$ simulating the universal TM, I'm done. What I'm ...
Dmitry's user avatar
  • 345
1 vote
0 answers
31 views

What are practical applications for markovs algorithm(string rewriting systems)

:) Currently I am browsing through the internet on the hunt for a topic for my bachelors thesis. Whilst being on Reddit I discovered an interesting repo (https://github.com/mxgmn/MarkovJunior) for a ...
Matplayerino's user avatar
0 votes
0 answers
117 views

What is the most computationally efficient Turing complete system?

I'm making a program that involves making models of and working with arbitrary systems (or programs). What is the most computationally efficient Turing complete system to model these in? By "...
user149991's user avatar
0 votes
1 answer
86 views

What does it mean for a machine language to be Turing-complete?

I was reading the Wikipedia article on Turing completeness, but I was having a hard time putting together all of the concepts. In simple terms, what does it mean for an instruction set to have Turing-...
Meester Moo's user avatar
6 votes
2 answers
457 views

Do all Turing-complete programming languages have to contain infinite loops?

Intuitively, it seems that if a programming language is Turing-complete, then it must contain a program that's an infinite loop. I have formalized this below: Conjecture. There does not exist a set $...
Theemathas Chirananthavat's user avatar
2 votes
1 answer
128 views

is HaltingFuck computable?

A while ago I defined the language HaltingFuck, but I've never been able to figure out its computational class. The language is defined as follows: HaltingFuck is a language very much like Brainfuck, ...
Silver's user avatar
  • 407
1 vote
1 answer
82 views

Encoding Turing machine-like behavior using families of sequences of vector spaces and modules. P=NP related

Let $F$ be a field. Suppose we have a machine $T$ that works with words that are elements of $F$, for exmaple $F = \Bbb{Z}/2, \Bbb{Q}$ (using arbitrary precision arithmetic), or $\Bbb{Z}/p$ for a ...
Daniel Donnelly's user avatar
2 votes
0 answers
79 views

Limited number of calling for a decision blackbox to compute all the solutions

I am trying to reduce between a solution problem and a decision version of the same problem. The problem is the orthogonality problem. Given $2$ sets $L$ and $R$, whose size each is $n$ vectors over $\...
Dan D-man's user avatar
  • 514
4 votes
1 answer
576 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: ...
hehehe's user avatar
  • 43
1 vote
1 answer
104 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 ...
dlee1828's user avatar
1 vote
1 answer
149 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 ...
Dan's user avatar
  • 61
0 votes
0 answers
48 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 ...
Dan's user avatar
  • 61
0 votes
0 answers
71 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 ...
Anon21's user avatar
  • 345
5 votes
3 answers
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 ...
Dan's user avatar
  • 61
1 vote
3 answers
547 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 ...
Sergio's user avatar
  • 11
12 votes
8 answers
3k 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 ...
Trev's user avatar
  • 296
-1 votes
2 answers
56 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 ...
Trev's user avatar
  • 296
11 votes
2 answers
3k 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 ...
emanresu A's user avatar
1 vote
1 answer
207 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 ...
DannyNiu's user avatar
  • 192
4 votes
0 answers
99 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}$) ...
Sid Mani's user avatar
-1 votes
1 answer
111 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 ...
Glubs's user avatar
  • 23
2 votes
2 answers
157 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&...
polcott's user avatar
  • 87
0 votes
1 answer
1k 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 ...
younes zeboudj's user avatar
5 votes
1 answer
979 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 ...
Ski Mask's user avatar
  • 463
2 votes
0 answers
266 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: ...
Andreas Leto's user avatar
2 votes
1 answer
78 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 ...
Java Machine's user avatar
20 votes
2 answers
6k 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....
MWB's user avatar
  • 495
1 vote
1 answer
281 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 ...
gilch's user avatar
  • 111
9 votes
3 answers
1k 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 "...
Max Heiber's user avatar

1
2 3 4 5