raoofha/haltingproblem

halting problem

haltingproblem's Issues

Does -0 (negative zero) makes everything decidable ?

in lambda calculus we can define -0 as (λf.λy.y) and 0 as (λf.λn.n), can we use this as a way to solve undecidable problem?

Can we define a halting function using this special turing complete subset of javascript ?

using the following functions only

{
let enc = (a) => { if(typeof(a) === "bigint" || a === undefined) return a || 0n; else if (typeof(a) === "string") return BigInt("0x"+Array.from((new TextEncoder()).encode(a)).map((c)=>c.toString(16).toUpperCase().padStart(2,"0")).reverse().join("")); else throw new SyntaxError(); }
div = (a,b) => { if((typeof(a) === "bigint" || a === undefined || typeof(a) === "string") && (typeof(b) === "bigint" || b === undefined || typeof(b) === "string") ) try{ return (enc(a)/enc(b)); }catch(e){ if(typeof(a) === "string") { throw a; } else { throw a || 0n; } } else throw new SyntaxError(); }
sub = (a,b) => (enc(a)-enc(b))
mul = (a,b) => (enc(a)*enc(b))
}

and a main function of the form

main = (...) => main(...)

it seems to me that we can define a halting function

Why all models of computation are colorless?

halting problem is usually defined like this

$$\begin{align*} h(m,n) &= \begin{cases} 1 & \text{if turing machine $m$ halts on input $n$} \\\ 0 & \text{otherwise} \\\ \end{cases} \end{align*}$$

but if we define it like this

$$\begin{align*} h(m,n) &= \begin{cases} \color{green}{0} & \text{if turing machine $m$ halts on input $n$} \\\ \color{red}{0} & \text{otherwise} \\\ \end{cases} \end{align*}$$

and use $\color{green}{0}$ and $\color{red}{0}$ as blank symbols and make them indistinguishable then diagonalization argument does not work because it is possible that there is a turing machine that output $\color{green}{0}$ or $\color{red}{0}$ for solving the halting problem

Is Blindfolded Arithmetic (and its variants) Decidable ?

is there a Godel like sentence for Blindfolded Arithmetic (and its variants where there are unlimited number of registers and instruction can contains numbers and subtraction is truncated-subtraction) ?

why Godel came up with the Godel's sentence in the first place while according to Wikipedia he was interested in Leibniz Characteristica universalis: "The logician Kurt Gödel, on the other hand, believed that the characteristica universalis was feasible, and that its development would revolutionize mathematical practice (Dawson 1997)"

is this set decidable?

considering these set of numbers

$$ H_0 = \lbrace m | \text{$m$ is a turing machine and does not halt on blank input} \rbrace $$

$$ G = \lbrace m | \text{$m$ is a turing machine and does not halt on $m$} \rbrace $$

$$ L = H_0-G $$

is $L$ decidable ?

Does diagonalization argument works for call by value lambda calculus ?

it seems that diagonalization argument does not work for call by value lambda calculus
so we can have a lambda abstraction that takes Godel number of a lambda term as input and evaluate to 1 or 0 depending on whether the lambda term has a normal form or not

Is "LOOP + error instruction" turing complete ?

it seems like that if we add an error instruction to LOOP programming language it becomes turing complete because as far as I know all proof for total but not primitive recursive functions rely on diagonalization, and the argument that the LOOP+error can not compute the Ackermann function is invalid because a universal program is a function from String to String so you have to consider that when you want to compute a function from N to N

Is <N,/,*,-> (Natural numbers,division,multiplication,subtraction) a basis for the set of partial recursive functions ?

it seems to me that div, mul and sub can compute the set of partial recursive functions

Does the set of all partial and total computable functions have a basis ( using division by zero as the source of partiality instead of recursion/iteration/jump ) ?

in this book they wrote

The class of partial recursive functions does have a basis. 
This follows from the existence of a universal Turing machine. 
The function associated with the universal Turing machine, 
together with a few other elementary functions gives a basis for the partial recursive functions

so if there is a universal function from String to String that use division by zero or similar partial function to compute it's value then we have total and turing complete language that can compute partial functions

Is there a universal Diophantine polynomial with two parameters and zero unknowns ?

it seems to me there must be a universal Diophantine polynomial with two parameters and zero unknowns

Does undecidability imply unsolvability ?

it seems to me that undecidability does not imply unsolvability
imagine we have a partial solution to the totality problem (the problem of determining whether a given computer program will halt for every input) meaning we have a semi-algorithm that correctly halt on most but not all of it's input, let's call it isTotal_0 then we can write the following program to solve the totality problem

function isTotal(p)
{
  q = substn(isTotal,p);
  if(isTotal_0(q))
  {
    return isTotal_0(p); 
  }
  else
  {
    console.log(0);
    while(1);
  }
}

then we can solve the halting problem using isTotal

function h(p,n)
{
  return isTotal(substn(p,n));
}