comment
Expressing functions using the arithmetic dictionary
I'm not sure I understand what "expressed" means here. For one definition I have in mind I think its planely false. The other definitions I have in mind all add something you're not stating here.
comment
Expressing functions using the arithmetic dictionary
Can you define the elements of that "dictionary"? I suspect that the general recursive functions is what you're basically looking for: en.wikipedia.org/wiki/General_recursive_function
comment
Enumerating every "partnering" without repeating partners
Gah that algorithm is so simple. Why didn't I think of it?
revised
Enumerating every "partnering" without repeating partners
technical correction
Loading…
Loading…
Loading…
Loading…
comment
If a turing machine can't solve the halting problem for a machine X, does this imply that X is at least as powerful as a turing machine?
This question misses a key logical point. Classically speaking every Turing machine either halts or loops so for any specific Turing machine $M$ you can always write another Turing machine that always accepts or always rejects $H$ and thus $H$ will accept IFF $M$ halts.
comment
Decidability of equality, and soundness of expressions involving elementary arithmetic and exponentials
At the moment I'm not sure how adding exp/ln changes things but Tarski's theorem and a bit of work lets (with a clever encoding of division) lets you work out if two such expressions are equal absent exp/ln. Also decidability of computeable reals/algebraics doesn't matter here. You're really asking something more akin to unification or a problem in logic Doesn't mean I have an answer yet.
awarded
comment
Halting problem theory vs. practice
Nice! Good to know about this. I might give this a try and see how useful it is in practice. I wonder if this isn't a lot more useful in practice than the functional stuff I'm aware of.
comment
building a polynomial algorithm that solves SAT when given a polynomial TM that solves SAT on two formulas
hint: Can you make a formula that is UNSAT iff the input formula is SAT?
revised
Loading…
awarded
revised
Halting problem theory vs. practice
added tags
Loading…
answered
Loading…
comment
Is there a way to hash a turing machine?
The basic primitive that I like to use here is called a pairing function: en.wikipedia.org/wiki/Pairing_function
comment
Boolean algebraic expression vs Propositional logic expression
The paragraph on "Intuitionistic logic systems tend ..." is wrong to misleading at best. 1) They don't tend to be decidable unless you mean proof check is decidable in which case so do classical systems. Generally intuitionistic systems are equiconsistent with their classical counterparts and you can convert classical statements into equiprovable forms in an intuitionistic logic via something like double negation translation. 2) Type checking being decidable doesn't avoid Godel-like incompleteness. You can apply Godel's proof just fine to any intuitionistic logic (such as Heyting algebra)