Questions tagged [turing-machines]

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

Filter by
Sorted by
Tagged with
41
votes
7answers
4k views

Truly random number generator: Turing computable?

I am seeking a definitive answer to whether or not generation of "truly random" numbers is Turing computable. I don't know how to phrase this precisely. This StackExchange question on "efficient ...
38
votes
7answers
6k 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. ...
49
votes
2answers
7k views

Realizability theory: difference in power between Lambda calculus and Turing Machines

I have three related subquestions, which are highlighted by bullet points below (no, they could not be split, if you are wondering). Andrej Bauer wrote, here, that some functions are realizable ...
18
votes
2answers
3k 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 ...
50
votes
5answers
21k views

Relationship between Turing Machine and Lambda calculus?

Is there a relationship between the Turing Machine and the Lambda calculus - or did they just happen to arise about the same time?
45
votes
5answers
2k views

Historical reasons for adoption of Turing Machine as primary model of computation.

It's my understanding that Turing's model has come to be the "standard" when describing computation. I'm interested to know why this is the case -- that is, why has the TM model become more widely-...
20
votes
3answers
2k 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 ...
40
votes
2answers
2k views

Alphabet of single-tape Turing machine

Can every function $f : \{0,1\}^* \to \{0,1\}$ that is computable in time $t$ on a single-tape Turing machine using an alphabet of size $k = O(1)$ be computed in time $O(t)$ on a single-tape Turing ...
30
votes
4answers
4k views

Can a probabilistic Turing machine solve the halting problem?

A computer given an infinite stream of truly random bits is more powerful than a computer without one. The question is: is it powerful enough to solve the halting problem? That is, can a ...
19
votes
3answers
1k 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 I'...
15
votes
3answers
740 views

Can it be determined if language L lies in NP?

Given a language L defined by a Turing Machine that decides it, is it possible to determine algorithmically whether L lies in NP?
12
votes
1answer
421 views

Time Hierarchies in DSPACE(O(s(n)))

The time hierarchy theorem states that turing machines can solve more problems if they have (enough) more time. Does it hold in some way if the space is limited asymptotically? How does $\textrm{DTISP}...
32
votes
6answers
6k 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 ...
1
vote
2answers
1k views

Is there an alternative proof of the TM Halting Problem other than the “standard” one? [closed]

I'm wondering if anyone is aware of a proof of the Halting Problem that is not just a permutation of the "standard" proof. Since there are so many formulations of this proof, rather than pick a ...
6
votes
3answers
760 views

What does it mean that there are differing views on how computations are represented on the Turing Machine?

For a given algorithm (eg reverse the items in this list) and a given type of Turing machine (eg the 3-state 2-symbol busy beaver reduced to 5-tuples) - is there a single simplest way that this ...
28
votes
2answers
3k 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 ...
27
votes
4answers
5k views

Church's Theorem and Gödel's Incompleteness Theorems

I have recently been reading up on some of the ideas and history of the ground-breaking work done by various logicians and mathematicians regarding computability. While the individual concepts are ...
21
votes
2answers
8k views

How is proving a context free language to be ambiguous undecidable?

I've read somewhere that a Turing machine cannot compute this and it's therefore undecidable but why? Why is it computationally impossible for a machine to generate the parse tree's and make a ...
29
votes
1answer
864 views

Is there a reasonable automated proof system for TCS theorems?

Suppose I wanted to formalize Turing's proof regarding the halting problem so that a machine could check it. Some of the well-known automated theorem proving systems include Mizar, Coq, and HOL4. I ...
26
votes
4answers
1k views

Is there a non Turing-complete model of computation whose halting problem is undecidable?

I cannot think of any such model, maybe some form of typed lambda calculus? some elementary cellular automaton? This would almost disprove Wolfram's "Principle of Computational Equivalence": ...
28
votes
6answers
2k views

Maximum computational power of a C implementation

If we go by the book (or any other version of the language specification if you prefer), how much computational power can a C implementation have? Note that “C implementation” has a technical meaning:...
11
votes
3answers
1k 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 "...
6
votes
8answers
5k 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?
20
votes
2answers
934 views

$\ell_p$-norm preserving Turing machines

Reading some recent threads on quantum computing (here,here, and here), make me remember an interesting question about the power of some kind of $\ell_p$-norm preserving machine. For people working ...
13
votes
2answers
2k views

Oblivious Turing Machine emulation lower bound

Is there a proof that the emulation of a Turing machine on an 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 ...
5
votes
2answers
4k views

Are there other computer architectures apart fom the von neumann /turing architectures?

Are there other computer architectures apart from the Von Neumann /Turing architecture?
10
votes
1answer
293 views

Is this language recognizable by a 3 symbols TM in O(n log n)?

I was playing with the very interesting and still open question "Alphabet of single-tape Turing machine" (by Emanuele Viola) and came up with the following language : $L = \{ x \in \{0,1\}^n \text{ s....
6
votes
1answer
137 views

Is $L \subset 1NL$ when $L \neq NL$?

A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which ...
4
votes
0answers
77 views

Libraries for programming automata and Turing machines

What are the most useful libraries around for coding related to automata and Turing machines? By useful I mean the number of functions and algorithms supported by it.
2
votes
0answers
80 views

Is there a DCSL that cannot be recognized in O(n^2) steps by a deterministic LBA?

Is there a context sensitive language $L$ so that $L$ cannot be recognized by a deterministic linear bounded turing machine in $O(n^2)$ steps, but still can be recognized by a deterministic LBA? The ...
13
votes
1answer
3k 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 ...
6
votes
0answers
506 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 halt?...
3
votes
1answer
112 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 ...
2
votes
0answers
195 views

Turing Machine which generates order on the set of its states

The Turing machine (TM) is an abstract model for effective implementation of (finite algorithmic) calculation. TM is defined over some alphabet of symbols L and reading data performs a finite sequence ...
6
votes
0answers
109 views

Small universal monotone Turing machines

This paper surveys small universal Turing machines. What are some examples of small universal monotone Turing machines, as described by Schmidhuber? Which of these are efficient (polynomial time) ...
4
votes
1answer
2k views

Simulating Turing machines (output included) with circuits

A Turing machine with input alphabet {0,1} computes a partial or total function $f \colon \{0,1\}^* \to \{0,1\}^*$. Is it possible to construct a circuit family $\{C_n\}$ such that for an input $x$ of ...
4
votes
1answer
425 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
756 views

Is there any proof that a network made of Turing machines can't solve the halting problem? [closed]

My question points to the fact that Turing machines are isolated by definition. But what if they can send and receive information from/to other Turing machines? What if they can be "interrupted" at ...