The turing-machines tag has no wiki summary.
4
votes
3answers
116 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 ...
-3
votes
0answers
56 views
Halting problem? [closed]
I have some concerns about the Halting problem. This is the proof I know:
Let $h(M, i)$ be a function, $M$ being Turing machine and $i$ input for the Turing machine. Let $h(M, i)$ output true ...
-2
votes
0answers
25 views
construct a TM from a PDA [migrated]
Given a PDA $P=(Q,\sum,\delta,q_0,F)$ construct formally a TM that accepts $L(P)$.
My idea is to construct a Turing machine with 2 tapes, one for the input and the other for the stack. Also to add ...
-1
votes
0answers
62 views
Undecidability of whether a given TM has only mechanically detectable loops or always halts [migrated]
This might be a bit of an abstruse question, but it's something I've been trying to prove.
I'm trying to show that it is undecidable whether a given Turing Machine is a member of the set of all ...
0
votes
0answers
88 views
Is there a way to transform a Turing machine into an oblivious turing machine that decides the same langauage?
Suppose you have turing machine M that decides L. Is there a simple way to convert this turing machine into an oblivious turing machine M' that decides the same language? My intuition says yes but i ...
1
vote
0answers
114 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 ...
10
votes
1answer
228 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
169 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
131 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 ...
0
votes
2answers
104 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 ...
2
votes
2answers
472 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 ...
3
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
179 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
102 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
318 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 ...
3
votes
2answers
255 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 ...
-4
votes
1answer
206 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
126 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 ...
6
votes
0answers
101 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 ...
-8
votes
2answers
205 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 ...
21
votes
7answers
3k 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
248 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?
10
votes
1answer
510 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 ...
-2
votes
2answers
221 views
Are humans merely Turing complete? [closed]
Simply as stated in the question. Are humans merely Turing complete, or are we somehow "better" (or "worse") than a Turing complete machine? Why? How would one determine this?
10
votes
3answers
874 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 ...
1
vote
1answer
293 views
Definition of a prefix-free Turing machine
A prefix-free function is one whose domain is prefix-free.
Similarly, a prefix-free (Turing) machine is one whose domain is
prefix-free. It is usual to consider such a machine as being
...
9
votes
3answers
923 views
Does P contain incomprehensible languages? (TCS community wiki)
Answer: not known
Many thanks to all who helped refine this question and the definitions associated to it.
The definitions of this wiki provided the starting point for the more recent TCS wiki ...
2
votes
2answers
492 views
Is a turing machine with random number generator more powerful?
Let's extend the Turing machine so that it can read from a stream of random number generators (in addition to an infinite tape to read and write). Certainly the TM with randomness can do whatever a ...
4
votes
0answers
101 views
How is Cooks overlap argument applied in Vitányi's theorem?
In P.M.B. Vitányi, Relativized Obliviousness, MFCS'80 paper one can read that the proof of Theorem 1 is based on the overlap-argument of Cook, however I don't see how this argument is applied.
The ...
9
votes
3answers
699 views
Why do we use single tape Turing machines for time complexity?
As you know there are many anomolies for the single tape Turing machines when the time is $o(n^2)$: multi-tape TM simulation, simulation of larger tape alphabet with just $\{0,1,b\}$, time ...
8
votes
2answers
584 views
Oblivious Turing Machine emulation lowerbound
Is there a proof that the emulation of a turing machine on a oblivious turing machine can't be done in less than $\mathcal{O}\left(m\log m\right)$ where $m$ is the number of steps the turing machine ...
3
votes
1answer
204 views
Abstract definition of universal computation
There are many universal computation systems. Turing machines, tag systems, rewrite systems, cellular automata to name just a few. The universality of a system is proved via reduction from a known ...
-5
votes
1answer
187 views
Does a Non deterministic TM halt after the same number of steps on the same input? [closed]
Let $M$ be a Turing Machine (TM) which decides a certain language. Enter an input $x$ to $M$ and let the machine compute on $x$. After some time, $M$ will halt.
If $M$ is a deterministic TM, it will ...
3
votes
0answers
167 views
Are there connections between Turing machines and symbolic dynamic systems?
On a course, when shift systems were being introduced, the lector said that "if the shift of symbols sequence reminds you Turing machine, then it is a very correct association":
$\sigma(\ldots, ...
4
votes
2answers
430 views
Transition Diagram of a Universal Turing Machine
I have searched the web for the transition diagram of a universal Turing machine without luck. Is anyone aware of such a diagram? I need this as a reference, so preferably a book or a published ...
17
votes
5answers
1k views
What's the simplest noncontroversial 2-state universal Turing machine?
I'm wanting to encode a simple Turing machine in the rules of a card game. I'd like to make it a universal Turing machine in order to prove Turing completeness.
So far I've created a game state ...
13
votes
3answers
673 views
Is the concept of the Turing Machine derived from automata?
I was just recently having a discussion about Turing Machines when I was asked, "Is the Turing Machine derived from automata, or is it the other way around"?
I didn't know the answer of course, but ...
3
votes
2answers
204 views
Finding the Length of the shortest Accepting path of a NDTM
Let $M$ be a NDTM (non deterministic Turing machine) which decides a certain NP-complete language, say SAT.
$M$ computes any instance $I$ of the NP-complete problem in at most $p(n)$ non ...
2
votes
1answer
207 views
Is every busy beaver strictly monotonic asymptotically?
To be specific, let me first define the busy beaver function BB(n)= maximum number of 1's that can be printed on the tape (i.e., the maximum score) by a standard n-state, 2-symbol (0 and 1) Turing ...
-2
votes
1answer
429 views
Is there any proof that a network made of Turing machines can't solve the halting problem?
My question point to the fact that Turing machines are isolated by definition, but what if they can send, and receive information from/to to other Turing machines, what if they can be "interrupted" at ...
16
votes
3answers
1k views
If an abstract machine can simulate itself, does that make it Turing complete?
For instance, in programming languages it's common to write an X-in-X compiler/interpreter, but on a more general level many known Turing-complete systems can simulate themselves in impressive ways ...
12
votes
1answer
1k views
Can chess simulate a Universal Turing Machine?
I am looking to get a definite answer to title question.
Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white ...
0
votes
0answers
328 views
Can one write useful programs in Turing machine language? [closed]
In other words, could one theoretically design a turing machine that does everything the shell program sed does?
5
votes
1answer
135 views
A notion of time for uniform circuits
Let C={Cn} be a family of uniform boolean circuits, whose size and depth are bounded by functions s(n) and d(n).
What is the upper bound on the running time of a Turing machine M that evaluates C? ...
2
votes
1answer
176 views
Terminology for types of universal computation
Some models of computation are universal in the sense they can compute any arbitrary computable function $f:\mathbb{N} \rightarrow \mathbb{N}$.
Other models are universal only as far as the input and ...
8
votes
5answers
583 views
Distributed Turing Machine?
I'm a master student focused on distributed systems but also interested on theoretical computer science. I was wondering if there is a formal representation of a distributed system on top of a turing ...
5
votes
0answers
308 views
How fundamental is undecidability? [closed]
What does it mean that some problem is undecidable?
For instance the halting problem.
Does it mean that humans can never invent a new technique that always decides whether a turing machine will ...
13
votes
3answers
492 views
Is there a name for “physical things out of which one can build a Turing machine”?
One of the amazing things about computer science is that the physical implementation is in some sense "irrelevant".
People have successfully built computers out of several different substrates -- ...
0
votes
0answers
229 views
What's the relationship between state machine, Turing completeness, and modern computer ? [closed]
I'm not major in computer science.
5
votes
1answer
301 views
Busy Beavers: quadratic relation of output size and running time?
When glancing at the running times and output sizes of some Busy Beaver candidates on this page, I find that there seems to be a rough (up to some small power of 10) quadratic relation between output ...
