This tag is suited for questions involving Turing machines. Not to be confused with finite state machines and finite automata.
Questions tagged [turing-machines]
919 questions
57
votes
2 answers
Are there any Turing-undecidable problems whose undecidability is independent of the Halting problem?
To be more specific, does there exist a decision problem $P$ such that
given an oracle machine solving $P$, the Halting problem remains undecidable, and
given an oracle machine solving the Halting problem, $P$ remains undecidable?
David Zhang
- 8,582
- 2
- 37
- 59
43
votes
5 answers
Why do we believe the Church-Turing Thesis?
The Church-Turing Thesis, which says that the Turing Machine model is at least as powerful as any computer that can be built in practice, seems to be pretty unquestioningly accepted in my exposure to computer science. Why? Do we have any more…
GMB
- 4,118
- 1
- 19
- 34
31
votes
5 answers
Exactly when and why can a Turing-machine not solve the halting problem?
I perfectly understand and accept the proof that a Turing-machine cannot solve the halting problem.
Indeed, this is not one of those questions that challenges the proof or result.
However, I feel that there is still something left to be explained…
Bram28
- 95,826
- 5
- 64
- 110
22
votes
2 answers
How do uncomputable numbers relate to uncomputable functions?
All the online resources that I've seen on uncomputable numbers assume that they're all irrational. But this doesn't seem to be required by the definition. Wikipedia, for example, says that "[un]computable numbers are the real numbers that can [not]…
Isaac King
- 407
- 3
- 6
20
votes
5 answers
How can Busy beaver($10 \uparrow \uparrow 10$) have no provable upper bound?
This wikipedia article claims that the number of steps for a $10 \uparrow \uparrow 10$ state (halting) Turing Machine to halt has no provable upper bound:
"... in the context of ordinary mathematics, neither the value nor any upper-bound of…
ronno
- 9,442
- 1
- 26
- 66
19
votes
4 answers
How can we know we're not accidentally talking about non-standard integers?
This question is mostly from pure curiosity.
We know that any formal system cannot completely pin down the natural numbers. So regardless of whether we're reasoning in PA or ZFC or something else, there will be nonstandard models of the natural…
N. Virgo
- 6,771
- 1
- 26
- 52
17
votes
3 answers
Why did nobody prove undecidability by the "too many problems" argument?
To the best of my knowledge, the two major breakthroughs in regarding negative
results in computation/recursion theory came in 1936 by Church and Turing.
They both prove that some variant of the Halting problem was undecidable.
However, a very…
Pål GD
- 945
- 7
- 14
16
votes
0 answers
What turmite runs the longest before becoming predictable?
When looking at 2D Turing machines, many of them eventually become predictable. For example, Langton's Ant, the champion 2-color 1-state turmite, develops a highway after 10,000 steps. Predictable behavior includes Traps (as in Worm Trails),…
Ed Pegg
- 20,313
- 5
- 38
- 124
16
votes
1 answer
What breaks the Turing Completeness of simply typed lambda calculus?
On the Wikipedia page about Turing Completeness, we can read that:
Although (untyped) lambda calculus is Turing-complete, simply typed lambda calculus is not.
I am curious as to what exactly makes a simply typed lambda calculus not Turing…
Erwan Aaron
- 817
- 1
- 8
- 21
15
votes
4 answers
How large is the set of all Turing machines?
How large is the set of all Turing machines? I am confident it is infinitely large, but what kind of infinitely large is its size?
Kevin
- 467
- 4
- 15
13
votes
3 answers
How do we know that the P versus NP problem is an NP problem itself?
I have been doing some research on the P versus NP problem. On multiple occasions, I have seen people say that the problem itself is an NP problem. I have been curious about how we know this. If we know that the problem is NP, then has anyone…
Bobjoesmith
- 165
- 1
- 4
12
votes
2 answers
The mother of all undecidable problems
It is usual to show that a problem P is undecidable by showing that the halting problem reduces to P.
Is it the case that the halting problem is the mother of all undecidable problems in the sense that it reduces to any undecidable problem? If the…
Bob
- 1,534
- 10
- 15
11
votes
4 answers
What is the difference between a shuffle and a permutation?
A shuffle is defined (at least in my class) as:
Let $x = x_1x_2 \cdots x_k$ and $y = y_1 y_2 \cdots y_k$ be words over the same alphabet $\Sigma$. We say that $x$ is a shuffle of $y$ (denoted $x \sim y$) if there exists a permutation $\pi$ of…
Kitalda
- 213
- 2
- 6
11
votes
1 answer
Show that the question "Is there life beyond earth?" is decidable
I was given a question to prove that there exists a turing machine that solves the question
Is there life beyond earth?
and is decidable. I actually don't understand how to show a turing machine decides this.
Thanks.
Lee
- 811
- 6
- 15
10
votes
10 answers
Text books on computability
I collected the following "top eight" text books on computability (in alphabetical order):
Boolos et al., Computability and Logic
Cooper, Computability Theory
Davis, Computability and unsolvability
Hermes, Enumerability, decidability,…
Hans-Peter Stricker
- 17,751
- 7
- 59
- 128