# Tag Info

### 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 ...
• 161k

### 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 ...
• 22.3k

### 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 ...
• 30.5k
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, ...

### 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.
• 30.5k

### 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 ...

### 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 ...
• 15.8k
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 ...
• 402
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 ...
• 15.8k
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 ...
• 2,157
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: ...
• 30.9k