The Turing machine is a fundamental model of computation, especially in theoretical work.

learn more… | top users | synonyms

0
votes
0answers
60 views

What would a PDA be with a queue instead of a stack?

A while ago it occurred to me that the stack data model in a push-down automaton could be exchanged for a queue or deque model. I've explored this a bit as a pet project and it looks like an automaton ...
2
votes
0answers
75 views

Space time lower bound with $\mathsf{PSPACE}$ oracle

Does a single tape Turing machine with access to $\mathsf{PSPACE}$ oracle needs more than $\mathsf O(1)$ working tape memory and $\mathsf O(1)$ working time to solve $\mathsf{NP}$-complete problem? ...
1
vote
0answers
37 views

Analogues of different complexity classes in various models

We suspect following relation: $$TC^0\subsetneq NC^1\subsetneq L\subsetneq NL\subsetneq AC^1\subsetneq NC^2\subsetneq P\subsetneq NP\subsetneq PH\subsetneq PSPACE$$ in Turing/boolean circuit ...
1
vote
1answer
115 views

Is Redis Turing Complete?

Is Redis with all its data types (Strings, Lists, Hashes, Sets, Sorted Sets, etc.) Turing Complete?
0
votes
1answer
48 views

Is multiprocessing possible on a Turing Machine? [closed]

I recently created a parallel implementation of the Merge Sort, in which the sorting of several groups was accomplished by different processes, and was wondering if this was theoretically possible on ...
4
votes
0answers
86 views

What is the Kolmogorov complexity of arithmetic?

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(n) > L$ where $K(n)$ is the Kolmogorov complexity of the number $n$ and $L$ is a sufficiently large ...
7
votes
0answers
108 views

What can you do with a moving knife besides cutting a cake?

In the fair cake-cutting, two different computational models are used: A discrete model, in which the algorithm issues queries to the players and proceeds according to their replies; A continuous ...
17
votes
2answers
790 views

What functions can System F not compute?

In this wikipedia article on Turing Completeness it states that: The untyped lambda calculus is Turing complete, but many typed lambda calculi, including System F, are not. The value of typed ...
7
votes
1answer
229 views

Was bombe machine turing complete?

In the recent movie called The Imitation Game, there is a affirmation that Turing was building his theoretical machine. That machine is the Bombe Machine. Is this machine really equivalent to a Turing ...
2
votes
1answer
90 views

Simple example of halting-unprovable Turing machine

Is there a simple example of a Turing machine $M$, such that whether $M$ halts or not on the empty input cannot be proved within the current mathematical system? Specifically, I'm curious whether ...
3
votes
0answers
47 views

Is there an easy way to improve this Tree Normal Form for Busy Beaver candidates?

In "Attacking the busy beaver 5" by Heiner Marxen and Jürgen Buntrock, an algorithm to create tree normal candidates is explained (it also contains a concise introduction of the relevant terms). If ...
1
vote
1answer
103 views

What are different definitions of Universal Turing-machine?

I am not sure what is the appropriate way for this, but I would like to collect different possible definitions/variants of Universal Turing-machines. Here are the ones I know, post below if you know ...
9
votes
2answers
376 views

Looking for Literature Source for Following idea

I am quite certain that I am not the first to entertain the idea that I am going to present. However, it would be helpful if I can find any literature related to the idea. The idea is to construct a ...
4
votes
1answer
81 views

Busy beaver candidate elimination: Minimum space requirements

I'm currently enrolled in a course that introduces Turing machines. As I wanted to play around a bit, I wrote a little TM engine and had it search for busy beavers (it successfully found the 4-state ...
0
votes
1answer
127 views

Where is the proof of universality of Rule110 in Stephen Wolfram's book?

I have Stephen Wolfram's book A New Kind Of Science. And I want to find the proof of the universality of Rule 110. I couldn't find the clue in the contents page since it only shows 12 chapters and no ...
0
votes
1answer
73 views

Conflicting definitions regarding TM and Recursively Enumerable languages

In Lewis's and Papadimitriou's book "Elements of the Theory of Computation" the transition table is a function $\delta: Q \setminus F \times \Gamma \rightarrow Q \times (\Gamma \cup \{L,R\})$. ...
3
votes
2answers
216 views

Source of Turing-machine illustration

I am writing a computer science textbook and want to use an illustration showing a Turing machine. Images are all over web, but almost always without authorship/illustratorship credited. I need to ...
1
vote
1answer
163 views

Does hyper-computational power of infinite time Turing machines also require infinite memory?

Can a infinite time Turing machine perform hyper-computation like checking the consistency of the set theory ZF without using infinite memory?
6
votes
2answers
1k views

A total language that only a Turing complete language can interpret

Any language which is not Turing complete can not write an interpreter for it self. I have no clue where I read that but I have seen it used a number of times. It seems like this gives rise to a kind ...
2
votes
0answers
57 views

Relation between the running time of Turing machines with different symbol sets

In Arora and Barak's Computational Complexity, Claim 1.5 says that if a function $f$ is computable in time $T(n)$ by a Turing machine with alphabet $\Gamma$ then it is computable in at most time ...
22
votes
3answers
3k views

P and NP classes explanation through lambda-calculus

In the introduction and explanation P and NP complexity classes often given through Turing machine. One of the model of computation is the lambda-calculus. I understand, that all of models of ...
-1
votes
2answers
92 views

Looking for menu-driven coding editor based on a programming language state machine [closed]

I'd like to know whether an application development environment exists that uses a menu-driven coding editor that employs a programming language state machine. This would mean that commands, variable ...
9
votes
1answer
306 views

Are there non-constructive proofs of existence of “small” Turing machines / NFAs?

After reading a related question, about non-constructive existence proofs of algorithms, I was wondering if there are methods of showing existence of "small" (say, state-wise) computation machines ...
8
votes
2answers
770 views

Turing machines whose termination is unprovable?

I have a naive question: does there exist a Turing machine whose termination is true but unprovable by any natural, consistent and finitely axiomatizable theory? I ask for a mere existence proof ...
2
votes
1answer
239 views

Is it worthwhile to try to prove a conjecture by mapping it to a Turing machine?

Lets assume the proof of a conjecture, for example, the famous Goldbach conjecture. Is it possible to try to prove or disprove such a conjecture by devising a Turing machine that accepts if the proof ...
1
vote
2answers
2k views

Difference between infinite state machines and turing machines

Finite state machines (FSM) are strictly less powerful than turing machines (TM). But this is not the case with infinite state machines (ISM). For example, every TM can be embedded into some ISM. ...
0
votes
1answer
119 views

Simulation of deterministic turing machines

What are the best known upper and lower bounds for simulating t steps of certain models of deterministic turing machines (1 tape, 1 tape with read only input tape, 2 tape, multi tape, with/without ...
4
votes
2answers
274 views

Simulation of every physical quantum system on quantum computer

Let me quote from the section 9.3 of Classical and Quantum Computation by Kitaev, Shen and Vyalyi. With high confidence, we may claim that every physical quantum system can be efficiently ...
3
votes
1answer
103 views

Program transformation using partial functions which preserve partial correctness

Much work has been done demonstrating that certain program transformations preserve particular properties. That is, for any program $P$ which has property $\alpha$, show that $P$ transformed under ...
5
votes
0answers
176 views

Regular languages in lambda calculus

With Turing machines, by imposing certain restrictions on the form of the transition function, one can get a machine that accepts only regular languages. I am wondering what is the counterpart in ...
0
votes
0answers
159 views

How to picture Non-Deterministic Turing machine seeking out boolean expression to satisfy examples

Traditionally, the boolean satisfiability problem is framed as, given a boolean formula, is there an assignment that satisfies the formula. I'm trying to look at this differently - from the ...
13
votes
1answer
631 views

Computing input length on a one-tape Turing machine

In connection with this question it occurred to me to wonder: what is the time complexity for a single-tape single-head Turing machine to compute the length of its input? To be specific, let's say ...
0
votes
1answer
79 views

Is refuting candidate deciders of the halting problem computable? [closed]

No Turing machine can decide whether any given Turing machine will halt for a given input. That is: If you give me a Turing machine which you claim can take a Turing machine and an input for that ...
7
votes
4answers
339 views

Is there a generalization of the GO game that is known to be Turing complete?

Is there a generalization of the GO game that is known to be Turing complete? If no, do you have some suggestions about reasonable (generalization) rules that can be used to try to prove that it is ...
1
vote
0answers
135 views

Learning about Nested Stack Automata

I want to learn about nested stack automata. However my efforts to find a suitable learning resource have so far been abortive: The Wikipedia article on nested stack automata is a stub. Alfred Aho's ...
9
votes
5answers
1k views

a small C-like language that turing machines can simulate

I am looking for a small language that helps 'convince' students that turing machines are a sufficiently general computing model. That is, a language that looks like the languages they are used to, ...
6
votes
0answers
163 views

The size of output in circuit complexity

In circuit complexity we have one circuit for each input size. The size of the output is determined solely by the size of the input. So it seems to me that taken in its strict sense there are ...
1
vote
0answers
96 views

Can emptiness of reversal-bounded counter languages be decided in time polynomial to the number of counters?

I was reading this paper, about the complexity of decision problems for reversal bounded counter machines. I got to Theorem 1 on Page 6. The theorem shows that there's a log-space NTM which can ...
0
votes
8answers
865 views

What are the simplest turing-complete systems? [closed]

Lambda Calculus is very simple. Are there even simpler turing-complete systems? Which is the simplest of them all?
5
votes
3answers
262 views

Computing Functions with Dynamical Systems

I was trying to make a set of differential equations "compute" some given function just like a Turing Machine does. Essentially, a given Turing Machine with an initial configuration (which includes ...
2
votes
0answers
145 views

Is it possible to simulate a Linear Bounded Automata with logic circuits where links have min-max bounded delays? I need a reference in the literature

Consider the following building blocks, which can be used to construct a logic circuit: basic logic gates {OR, AND, NOT} which have $n$ input and $m$ output pins, with $n,m\ge 1$. generators of ...
11
votes
1answer
471 views

Is $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$?

Define $\mathsf{DTIME}(f(n))$ as the class of languages that can be accepted by a (multitape) Turing machine in time $f(n) + 1$. (The "$+ 1$" is just to simplify notation and avoid confusion.) Notice ...
3
votes
2answers
218 views

Runtime of a TM enumerator

Is there a way to find out the time bound between 2 consecutive strings enumerated by a TM (the TM that decides this language is promised to run in linear time)? For simplicity let's say the string ...
3
votes
0answers
241 views

Insertion and deletion operations for Turing machines

A Turning machine with insertion and deletion operations can be simulated by an ordinary Turing machine with a quadratic time cost. Do we know how insertion and deletion fit into the polynomial time ...
-1
votes
2answers
146 views

iterations of a $\epsilon$-FSM transducer on a tape as equivalent to a TM computation

A question partly inspired by a recent question[1] on the utility of FSMs: Years ago noticed the following property of FSM transducers with $\epsilon$-transitions (which allow an "empty" transition ...
4
votes
2answers
1k views

Why were Finite Automata and Turing Machines created?

It seems the creation of Turing Machines and finite automata were apart by at least 2+ decades. That is TMs don't really reference FAs for their working and vice versa; TMs and FAs were developed ...
5
votes
4answers
3k views

Is there such a thing as a state-based programming language?

As anyone knows who has read Alan Turing's paper describing the Turing Machine (On Computable Numbers, With an Application to the Entscheidungsproblem), the syntax he uses is vastly different from ...
2
votes
1answer
351 views

Langton's ant highway conjecture and undecidability

I was recently reading about Langton's ant and the related conjecture which states that for every initial configuration, the ant eventually starts building a 'highway'. I also read that it has been ...
-3
votes
1answer
168 views

Can Turing Machine implements Strong AI? [closed]

It has been proved that a Turing Machine cannot solve the halting problem, but is it (being able to solve the halting problem) really necessary for implementing Strong AI ? We human can understand ...
1
vote
3answers
507 views

Does mathematical model for conccurent computations exist?

Turing machines can represent any computation. Can they also represent concurrent computations? Eg. multiple computations that can happen at the same time? If yes, how are the concurrent computations ...