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

learn more… | top users | synonyms

-1
votes
0answers
50 views

Show there exists a turing machine for the following language with these properties [on hold]

I'm struggling to understand a question I've been given. The question asks: Let $\psi$ be a boolean formula in $n$ variables. There are $2^n$ different combinations of assigning values to the ...
-1
votes
0answers
38 views

Turing machine's emptiness is undecidable How? [on hold]

So every Turing recognisable language has an enumerator. If i build a turing machine which uses the enumerator of language $L$ and accept it if it outputs anything and reject if it outputs nothing. ...
1
vote
1answer
74 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 ...
7
votes
2answers
323 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
66 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
116 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
66 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
180 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
124 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?
3
votes
2answers
391 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
46 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 ...
16
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
68 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
299 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
720 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
231 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
769 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
98 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
256 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
100 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
157 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
146 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
388 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
73 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 ...
3
votes
0answers
167 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
115 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 ...
8
votes
4answers
766 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
159 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
90 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 ...
-2
votes
8answers
528 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
195 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
141 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
464 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
210 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
209 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
140 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 ...
3
votes
2answers
868 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 ...
4
votes
4answers
2k 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
270 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
151 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
439 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 ...
2
votes
2answers
773 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
335 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
209 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
122 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 ...
-10
votes
2answers
355 views

is every “nontrivial” algorithm Turing-complete?

recently there was a big response here to a question relating to the Church-Turing thesis.[1] this is another question that has nagged at me for close to a decade after studying some areas of TCS ...
25
votes
6answers
4k views

Applicability of Church-Turing thesis to interactive models of computation

Paul Wegner and Dina Goldin have for over a decade been publishing papers and books arguing primarily that the Church-Turing thesis is often misrepresented in the CS Theory community and elsewhere. ...
-6
votes
1answer
356 views

why is a Turing machine defined as a 5-tuple? [closed]

[Edited to provide better context.] In a comment on meta, JɛffE suggested that this would be a good topic for a question to ask here. why is a Turing machine defined as a 5-tuple?
11
votes
1answer
734 views

Feasibility of Gödel machines

Recently I stumbled upon quite an interesting theoretical construct. A so called Gödel machine It's a general problem solver which is capable of self-optimization. It's suitable for reactive ...
10
votes
3answers
978 views

What type of automaton is Google's Turing Doodle?

In celebration of Alan Turing's birthday, Google published a doodle showing a machine. What kind of machine is the doodle? Can it express a Turing Complete language? There are obvious differences ...