Skip to main content
14 votes

What does it mean to prove the halting problem is undecidable "using arithmetization"?

I would guess/assume that by "arithmetization", they mean the concept that every Turing machine can be associated with a bit-string or natural number (the fact that we can encode a ...
D.W.'s user avatar
  • 161k
12 votes

What are the conditions necessary for a programming language to have no undefined behavior?

First off, let's be clear on what "undefined behaviour" is. In just C alone (and this is the understanding inherited by C++), there are two possible meanings, depending on which version of ...
Pseudonym's user avatar
  • 22.3k
8 votes

What are the conditions necessary for a programming language to have no undefined behavior?

The C language may say "if you do X, then whatever the result is, is not a violation of the C Standard". "Whatever the result is" can include the result that you hoped for, some ...
gnasher729's user avatar
  • 30.5k
8 votes
Accepted

Is the Turing machine the only framework to analyse limits of computation?

Turing machines are far from being the only model of computation considered by computer scientists. Among well-studied models of computation are: Turing machines, λ-calculus (and its many variants, ...
Jean Abou Samra's user avatar
7 votes

Is ChatGPT wrong about the definition of unrecognizable and undecidable languages?

ChatGPT is not capable of being “right” or “wrong” about anything. It is however capable of producing very plausible sounding nonsense about just any subject. Never trust anything it says.
gnasher729's user avatar
  • 30.5k
6 votes

Why can't we use computation history to detect looping of a Turing machine on a given input?

Detecting whether a machine $M$ is looping (meaning that it has reached the same configuration (not only of its internal state but also of the tape) twice), is indeed as "easy" as recording ...
Bernardo Subercaseaux's user avatar
6 votes

Is every non-recursively-enumerable language RE-hard?

Partial answer here: I think it at least depends on the chosen reduction. For example, consider $H\in \mathsf{RE}$ the halting problem. Then $\overline{H}\notin \mathsf{RE}$, but there is no many-one ...
Nathaniel's user avatar
  • 15.8k
5 votes
Accepted

Deciding whether a Turing machine decides a language $L$ in at most $n^2$ steps

This problem is indeed undecidable, assuming that $n$ is not a constant but refers to the length of the machine's input. Consider the problem $P$ of, given a Turing machine $\mathcal{M}$, to decide if ...
Rémi's user avatar
  • 402
5 votes
Accepted

Can I reduce a non semi decidable and undecidable language to a semi decidable and undecidable langauge? many-one reduction

It depends on the reduction. Using a Turing reduction, it is possible. For example, any problem $A$ is Turing-reducible to its complement $\overline{A}$, by puting a negation on an answer given by an ...
Nathaniel's user avatar
  • 15.8k
5 votes
Accepted

What are the conditions necessary for a programming language to have no undefined behavior?

The problem of statically detecting undefined behavior has nothing to do with undefinedness as such. It's just impossible to prove in general that programs in a Turing-complete language will do ...
benrg's user avatar
  • 2,157
5 votes
Accepted

What is the role of diagonalization in the proof of undecidability of the halting problem?

Unless you found an unusual proof, they're all refutations by contradiction (not "proofs by contradiction", although that is common parlance) and they all are qlso a form of diagonalization: ...
Andrej Bauer's user avatar
  • 30.9k
5 votes

Decidability of whether for a given $G$, $L(G)=\Sigma^+$? (or $L(G)=L$ where $L$ is fixed beforehand

It is decidable whether $\epsilon \in L(G)$. Given a context-free grammar $G$, you can construct a new context-free grammar $G'$ such that $L(G')=L(G) \cap \Sigma^+$. If $L(G')=\Sigma^+$ and $\...
D.W.'s user avatar
  • 161k
5 votes
Accepted

Undecidable problems in finite graphs

Given a graph class $\mathcal G$, computing the set of forbidden graph minors of $\mathcal G$ is undecidable. A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second Order ...
Pål GD's user avatar
  • 16.7k
4 votes

What are the conditions necessary for a programming language to have no undefined behavior?

So my question now is, what conditions need to be imposed on a Turing complete language in order to guarantee that all possible programs written in the language will have fully defined behavior ...
yeputons's user avatar
  • 256
3 votes

What does it mean to prove the halting problem is undecidable "using arithmetization"?

TLDR: It means that they are using a technique to represent Turing machines as numbers in order for the circularity to be possible, hence "arithmetization". It is not trivial (especially, it ...
Sam Gutkind's user avatar
3 votes

What are the conditions necessary for a programming language to have no undefined behavior?

Lets look at a sample program ...
QuadmasterXLII's user avatar
3 votes

What are the conditions necessary for a programming language to have no undefined behavior?

Starting from the C/C++ languages, ruling out all undefined behavior would be very hard. But if you're designing a language from scratch, it's not difficult at all to rule out undefined behavior. Many ...
Glenn Willen's user avatar
3 votes

A Turing machine for which it is impossible to predict whether it halts or not on a fixed input

For any specific machine $M_0$ and input $w_0$, there is a machine that decides whether $M_0$ halts on $w_0$. Indeed, one of the following machines works: The machine that outputs "Yes". ...
Yuval Filmus's user avatar
3 votes

Is matching pairs sufficient?

I assume that the Turing machine $M$ is allowed to be nondeterministic. In that case we need three positions. Consider the possibility that $M$ on a certain configuration may move either left or right....
Hendrik Jan's user avatar
  • 30.8k
2 votes

What could $P = NP$ imply about arbitrary Turing machines?

There is good evidence that what you are asking about does not occur. Specifically, there are computable $A,B$ such that $\mathsf{P}^A=\mathsf{NP}^A$ and $\mathsf{P}^B\not=\mathsf{NP}^B$ (this is the ...
Noah Schweber's user avatar
2 votes

"Term Rewriting and All That" - Exercise 2.3

I don't know what is the definition for a reduction to be decidable. I would expect it is one of the following two: Defn 1: $\to$ is decidable iff there is an algorithm $A$ that always halts and, on ...
D.W.'s user avatar
  • 161k
2 votes

Is explicitly explaining the case where the Turing Machine loops forever essential to proving reducibility?

Not only your professor is correct, but also the reduction is not well-written. Specifically, you did one of the following (and both are wrong): The reduction simulates the run of $M$ on $w$, and ...
Bader Abu Radi's user avatar
2 votes

Decidability terms clarification

Undecidable means "not decidable". They are synonyms. The definition is: we say that $L$ is undecidable if $L$ is not decidable.
D.W.'s user avatar
  • 161k
2 votes

Turing Machine language, Undecidable, reductions

Before doing reductions, it is good to have some intuitions about decidability: that helps to find which reduction can succeed. First, none of those two languages is recursive, because Rice's theorem ...
Nathaniel's user avatar
  • 15.8k
2 votes
Accepted

Undecidability of the exactly-1-in-k halting problem

Consider a Turing Machine $M_1$. Create $k - 1$ looping machines $M_2, …, M_k$ that never halts. Then $M_1$ halts on all inputs if and only if for any input, exactly one among $M_1, …, M_k$ halts. ...
Nathaniel's user avatar
  • 15.8k
2 votes
Accepted

Is it decidable if $\text{MIN}(L(G))$ and $\text{MAX}(L(G))$ is context-free for a context-free grammar $G$?

Ok so I think I figured it myself at last. In case of $\text{MIN}$ operation, for the sake of contradiction, let's assume it is decidable. Now let $(X = (x_1,...,x_n), Y = (y_1,...,y_n))$ be an ...
JimmyB's user avatar
  • 213
2 votes

Undecidable problems in finite graphs

Given $k$ pairs of source and sink nodes $(s_i,t_i)$, $i=1,\ldots,k$ in a network (directed graph), the multi-commodity flow problem asks whether we can simultaneously transport commodities from $s_i$ ...
Cheuk Ting Li's user avatar
1 vote

Is the Language of all encodings of Turing Machine that at least halts on one input and outputs 0 semi-decidable?

Since it seems like you are really uncertain about your own solution. Let's verify it step by step: 1- A is undecidable. To prove this statement, it is enought to show that there is a mapping ...
Ali Dastjerdi's user avatar
1 vote

Is the "intersection" of the special Halting Problem with a language always undecidable?

There is no general answer. $B$ could be decidable or undecidable, and $A$ could too, independently of $B$. This table contains different values of $B$ for all cases. $B$ decidable $B$ undecidable $...
Nathaniel's user avatar
  • 15.8k

Only top scored, non community-wiki answers of a minimum length are eligible