Halting problem theory vs. practice

It is often asserted that the halting problem is undecidable. And proving it is indeed trivial.

But that only applies to an arbitrary program.

Has there been any study regarding classes of programs humans usually make?

It can sometimes be easy to analyze a program and enumerate all of its degrees of freedom and conclude that it will halt.

For example, has there ever been an effort to create a programming language (scripting really) that guarantees halting? It would not be widely applicable but could still be useful for mission critical modules.

Why is the Halting problem decidable for Goto languages limited on the highest value of constants and variables?

This is taken from an old exam of my university that I am using to prepare myself for the coming exam:

Given is a language $ \text{Goto}_{17}^c \subseteq \text{Goto}$ . This language contains exactly those $ \text{Goto}$ programs in which no constant is ever above $ 17$ nor any variable ever above $ c$ .

$ Goto$ here describes the set of all programs written in the $ Goto$ language made up of the following elements:

With variables $ v_i \in \mathbb{N}$ and constants $ c \in \mathbb{N}$
Assignment: $ x_i := c, x_i := x_i \pm c$
Conditional Jump: if(Comparison) goto $ L_i$
Haltcommand: halt

I am currently struggling with the formalization of a proof, but this is what I have come to so far, phrased very casually: For any given program in this set we know that it is finite. A finite program contains a finite amount of variables and a finite amount of states, or lines to be in. As such, there is a finite amount of configurations in which this process can be. If we let this program run, we can keep a list of all configurations we have seen. That is, the combination of all used variable-values and the state of the program. If we let the program run, there must be one of two things that happens eventually: The program halts. In this case, we return YES and have decided that it halts. The program reaches a configuration that has been recorded before. As the language is deterministic, this means that we must have gone a full loop which will exactly repeat now.

No other case can exist as that would mean that we keep running forever on finite code without repeating a configuration. This means after every step, among our list of infinite steps, there is a new configuration. This would mean that there are infinite configurations, which is a contradiction.

Is this correct? Furthermore, how would a more formal proof look if it is? If not, how would a correct proof look?

Grammar and Enumerator for Decision and Halting Problem

in theoretical computer science I learned for every recursive enumerable language there would be an enumerator and a grammar. So since decision problem and halting problem are recursively enumerable, I was wondering what kind of grammar and enumerator could this be.

Ok since there exists a sequence of M_i I would start with M_1 and find all words for this TM and give them out. So if I have any TM is there a possibility to give all words out which are accepted by this TM? I probably would have to give all w_i to it and compute the first i words for i steps, then i+1 words for i+1 steps and so on. Or maybe something like DFS on all configurations. This really sounds like that only for one TM this could go on forever. So I would need to start the second TM for the same period of time after a while… Seems as if something similiar could work for Halting Problem. Do you have any more refined thoughts on this one?

But the Problem with the Grammar seems to be more challenging. How could I possibly come up with a Grammar for these problems? You would have to generate code(M_i) in such a way that its always in the language. So you would have to simulate the TM through grammmar on different words. It somewhat comes down to the question whether a TM accepts anything or holds on any entry. Or is it more "okay we proofed, so there must be some kind of grammar even though I can´t comeup with an idea for it".

Greets,

Felix

Confusion of halting problem

Show that the following problem is solvable.Given two programs with their inputs and the knowledge that exactly one of them halts, determine which halts.

lets P be program that determine one of the program will be halted.

P(Program x,Program y){      if(x will be halted)            then return 1;      else             then return 2; } 

since we know that exactly one of them will be halted,if 1 then program x will be halted.Otherwiae program y will be halted.

then we construct a new program call D

D(X,Y){       if(P(X,Y) == 2)           D will halt;        else           while(1)//D will not halt;    } 

lets S be aritbrary program.

So if we have D(D,S)

if D will halt then D will not halt

if D will not halt then D will halt

It impiles a contradiction same as halting problem.

But the question stated that it is solvable.

A variation of the halting problem

Given an infinite set $ S \subseteq \mathbb{N}$ , define the language:

$ L_S = \{ \langle M \rangle : M $ is a deterministic TM that does not halt on $ \epsilon$ , or, $ T_M \in S\}$

where $ T_M$ is the number of steps that $ M$ takes until it halts with the empty word $ \epsilon$ as input (or $ \infty$ if it doesn’t halt).

What are the sets $ S$ such that $ L_S$ is decidable?

There are some more trivial cases, if $ S = \{k,k+1,k+2, \dots \}$ for some $ k \in \mathbb{N}$ then $ L_S$ is clearly decidable, as we can simulate $ M$ on $ \epsilon$ for $ k-1$ steps and accept if and only if $ M$ accepts. though, if we take $ S= \{k,k+2,k+4,\dots \}$ for some $ k \in \mathbb{N}$ , or even simply taking $ S=\mathbb{N}_{even}$ or $ S=\mathbb{N}_{odd}$ this becomes more of a problem, because there is no prevention from it being impossible to have a finite calculation for whether the number of steps until halting will be even in the cases where it halts. Although this seems undecidable I’m not sure how to prove this.

I generally suspect that $ L_S$ is decidable if and only if $ \mathbb{N} \setminus S$ is finite

Are any two complexity classes equipped with an oracle to solve the halting problem equivalent?

Equip any complexity class $ C$ and $ B$ (to be more specific: any complexity class that contains only standard decidable problems) with an oracle $ O$ to solve the halting problem. Is $ C^O = B^O$ for any $ B$ and $ C$ that only contain problems decidable by a normal TM (meaning a TM with no access to an oracle (only the empty oracle))?

proving $E_{TM}$ is undecidable using the halting language

How to prove that:

$ E_{TM} = \{\langle M\rangle\mid M \ is\ a\ TM\ and\ L(M)=\emptyset\}\notin R$ (is undecidable)

using the language:

$ H_{halt}=\{(⟨M⟩,w):M\ halts\ on\ w\}$ .

I tried to prove by contradiction that assuming $ E_{TM}\in R$ I have a Turing machine which decides $ E_{TM}$ and to construct with it a turing machine which decides $ H_{halt}$ but I don’t know how to do so.

Halting problem – What if the halting algorithm gave more than one output?

Sorry I don’t know how silly a question this might be, but i’ve been reading up on the halting problem lately, and understand the halting problem cannot possibly output a value that is “correct” when fed a machine that does the opposite of itself. This therefore proves the halting problem cannot be solved by contradiction.

What if you were to give the halting algorithm 3 possible outputs, something like:

  • Yes
  • No
  • Non-deterministic (for paradox’s like this one)

You could argue then that for a non-deterministic output it would then do something entirely different, but this would be okay because it is still non-deterministic behavior. For a simple algorithm input, such as a while True: pass it would be incorrect to output non-determinism, since it will always be No.

I was wondering if this would change its solve-ability, or would it still be un-solvable?

Thanks for any responses

Zero-Sum Games and Halting Problem

Wikipedia states on the page of the halting problem, “For any program f that might determine if programs halt, a “pathological” program g called with an input can pass its own source and its input to f and then specifically do the opposite of what f predicts g will do.”

Suppose we have 2 neural networks, approximating f and g (allowing infinite size and depth limits). Is it wrong to assume that these two NNs can participate in a zero-sum game against each other, and that the Nash equilibrium (if it exists) of these 2 NNs contains the solution to the halting problem?

Can a halting configurations of a Turing Machine has the same state of another configuration has?

At first, I believed since the state a halting configuration is at will be a halting state, whenever a configuration goes into that state, the TM halts. Hence, there should not exist two configurations that appear at a different time that have the same current state.

However, after reading some introductions of the One-state Turing machine, I start getting confused about my initial conclusion since to my understanding, a one-state Turing machine will have its start state as accept state Can anyone explain this to me? Thank you!