New answers tagged computability
0
IDK if this is the most elegant way . But consider the language L = { : M is TM and L(M) =! emptyset and L(M) =! sigma*}
lets call the above language nontrivial now its quite easy to prove the nontrivial is not in both RE and coRE with reduction from ATM for example.
no that we have nontrivial we can use the following reduction :
F() =
from the ...
0
Hint 1: What happens when $k=2$?
Hint 2: Use a reduction from $\text{ALL}_{\text{TM}}$.
0
The function $g$ interprets $k$ as two inputs $k_1,k_2$. It runs $f(n,k_1)$ for $k_2$ steps, returns whatever $f$ does if $f$ halts, and returns $0$ otherwise.
1
The halting problem, $\mathsf{HALT}$ reduces to $\overline{L_2}$.
Given a TM $T$ and input $w$, create a new TM $N$ that on any input of length $n$, simulates $T$ on input $w$ for $n$ steps and then stops except that if $T$ ever halts before $n$ steps, $N$ will move its head to the right forever.
There is a gap in the above reduction. When $N$ simulates $T$...
1
Andrej's answer raises some excellent points. I think we can gain some additional insight by looking at why we demand the computable partial functions come with their natural domain in classical computability theory.
One benefit we get from this is that in Type-1 computability a string function computation can only provide garbage in a very limited way: It ...
3
Philosophical answer
The general philosophy in realizability theory (TTE is a special case of it) is that for a program $p$ realizes a map $f : A \to B$ then $p$, it should work correctly on realizers of arguments, i.e., if $r$ realizes $x \in A$ then $p\,r$ realizes $f(x) \in B$. It is quite unnatural to say anything about "non-realizers", for at least two ...
2
I don't know, but I suspect it's an open question.
If the theory of the reals with exponential function is decidable, then your problem is decidable, too. It is known that if Shanuel's Conjecture holds, then the former is decidable, so your problem is too.
If I understand correctly, the following paper tackles your problem:
The identity problem for ...
0
You are right, assuming $E_{TM}\in R$ you have Turing machine $T$ which decides $E_{TM}$ and you can construct with it a Turing machine which decides $H_{halt}$:
If we have $T$ which decides $E_{TM}$ and suppose we want to decide whether $M$ halts on $x$.
Construct a Turing Machine $T_{M,x}$ which irrespective of its input $y$ simulates $M$ on input $x$: if ...
1
Suppose that there is a Turing machine $T$ that decides $E_{TM}$.
Given a turning machine $M$ and an input $w$ you can construct a new Turing machine $M^*$ that decides whether $(M,w) \in H_{halt}$. $M^*$ operates as follows:
It first constructs a new Turing machine $M'$ that ignores its input, simulates $M$ on input $w$ and, once the simulation is ...
1
Yes. Actually, it is even true that for every language $L_1$ there is a language $L_2 \supseteq L_1$ such that $L_2$ is regular.
Proof: Pick $L_2 = \Sigma^*. \square$
1
Recall that a collection $\mathcal{F}$ of computable partial functions admits a computable numbering if there is a computable function $f : \mathbb{N} \to \mathbb{N}$ such that $\mathcal{F} = \{\varphi_{f(e)} \mid e \in \mathbb{N}\}$, where $(\varphi_e)_{e \in \mathbb{N}}$ is a standard enumeration of the computable partial functions.
Let $\mathcal{I}$ be ...
0
You cannot say that every total function is computable, since that is not true. For example, the function $f(n)$ which returns $1$ if the $n$'th Turing machine halts and $0$ otherwise is not computable.
However, the question is much simpler. The definition of a PRC class specifies several closure properties, of the form: if so-and-so belong to the class, ...
1
Suppose we allow an algorithm to return "Yes, it halts", "No, it doesn't halt", or "I don't know". Then the proof no longer applies; and in fact this modified version of the halting problem is decidable. For instance, a very simple algorithm could always output "I don't know", and it'd never be wrong. Unfortunately, that very simple algorithm probably isn'...
1
It doesn't matter if and when some newly defined machine $M$ outputs an extra value - the original machine $H$ of the halting problem still leads to a contradiction.
The proof of the halting problem relies on showing that if we assume there is an oracle machine $Q$ solving the halting problem that we can construct a machine $H$ that uses $Q$ such that a ...
1
No, they are not the same.
There are different equivalent representations for any problem (e.g. Turing machines, neural networks, differential equations, ...). But changing from one representation to another does not change whether the problem is fundamentally solvable - otherwise they would not constitute equivalent representations.
Zeno machines can be ...
1
Microsoft has developed a practical code checker (whose name escapes me at the moment) which performs halt-testing. It exploits the fact that the code it checks is human-written and not arbitrary, just as you suggest. More importantly, it bypasses the impossibility proof by being allowed to return the answer 'Cannot decide' if it runs into code too ...
16
Languages that are guaranteed to halt have seen wide spread use. Languages like Coq/Agda/Idris are all in this category. Many many type systems are in fact ensured to halt such as System F or any of its variants for instance. It's common for the soundness of a type system to boil down to proving that all programs normalize in it. Strong normalization is a ...
0
As stated in the comments, every problem is reducible to itself (under any notion of reduction - polynomial-time many-one reduction, polynomial-time Turing reduction, ...).
It's worth noting that when thinking about many-one reductions there are two important "edge cases" to consider:
No nonempty set is many-one reducible to $\emptyset$.
No set other than ...
0
Let $T$ be the set of all Turing machines.
Let $B = \{ (e,x, y) \in T \times \{0,1\}^* \times \mathbb{N} : e(x) \text{ halts in $y$ steps}\}$, and define $C = \{e \in T : \forall x \in \{0,1\}^*, \; \exists y \in \mathbb{N}, \; (e, x, y) \in B]$.
We start by proving $\text{TOT}=C$.
If $e \in \text{TOT}$ then, $\forall x \in \{0,1\}^*$, $e(x)$ halts. Let $...
2
Your first problem is $\mathsf{NP}$-Complete. Membership to $\mathsf{NP}$ is trivial. To see that it is $\mathsf{NP}$-hard, you can reduce it from Subset Sum. Let $\langle S_1, W_1 \rangle$ be an instance of Subset Sum. Define $S_2$ as the multiset obtained by multiplying each number in $S_1$ by $100$, and $W_2 = 100 W_1$. The instance for your problem is $\...
2
Sure. Any Turing machine can be represented as a bit string (print out the description of the Turing machine). Any bit string can be encoded as a natural number (prepend a 1 bit, and view it as a binary representation of a number).
1
To follow the strategy you outline, we need to be confident a priori that we have an upper bound on $BB(n)$. More snappily, if $f$ is any function with $f(n)\ge BB(n)$, then from $f$ we can compute the halting problem: given an $n$-state machine, run it for $f(n)$-many steps.
Since the halting problem isn't computable, this means that no such $f$ is ...
0
But this isn't a satisfactory answer because surely decidability isn't about how feasible a procedure is in practice, but whether it's decidable in theory - what if computers were powerful enough to be able to implement this in our current universe where BB(n) is very large?
The problem is not so much that BB(n) is very large, the problem is that it is not ...
Top 50 recent answers are included
