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

learn more… | top users | synonyms

0
votes
1answer
45 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 ...
3
votes
0answers
81 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
101 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 ...
12
votes
2answers
703 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
212 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
85 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
44 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
98 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 ...
8
votes
2answers
355 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
78 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
125 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
72 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
203 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
152 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?
5
votes
2answers
984 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 ...
19
votes
3answers
2k 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
80 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
304 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
751 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
237 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
1k 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
116 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
267 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
173 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
157 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
596 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
77 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
323 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
128 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
162 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
95 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 ...
-1
votes
8answers
740 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?
4
votes
3answers
235 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
468 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
215 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
231 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
143 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
965 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
328 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
162 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
492 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 ...
4
votes
2answers
1k views

Was Babbage's Analytical Engine really turing-complete?

According to literature, Babbage's Analytical Engine is turing-complete because it supports conditional branching: it can perform different operations depending on the sign of the result last ...
-3
votes
1answer
368 views

Minimal Turing Machine implementation / Von Neumann UC [closed]

I've written a small python program which implements a Turing Machine with a finite tape. It has a tape, a head, a state register and a set of transfer functions ("the program"). The difference to a ...
6
votes
0answers
217 views

Data structures lower bounds on Turing machines

Have there been any results on lower bounds for implementing data structures on Turing machines, e.g. stacks, queues, etc ? I guess that people are mostly interested in models with random access, but ...
7
votes
0answers
131 views

The power of randomized logspace with two-way access to the random tape

Let $\mathsf{ZPL}$/$\mathsf{RL}$/$\mathsf{BPL}$ denote the classes of the languages which are accepted (with zero/one-side/two-side error) by a logspace Turing machine with one-way access to the ...