= 27d567bc2d48d9f40e9ccc20ea370b15)
MrMind comments on Defining causal isomorphism - Less Wrong Discussion
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (15)
Let's start small. Since we are talking about algorithms (better yet, about programs of a universal Turing machine), what about if two programs can match the same input on the same output?
Would that suffice as a definition of isomorphism, even if they have wildly different resource usages (including time)?
What if they don't output anything?
Sadly, even that is unprovable - I believe there's a way to convert a solution for this problem to one for the halting problem.
Of course you can still do it for a large fraction of functions you're likely to see in real life.
Yes -- It's not possible to decide, given two programs, if they have identical behavior. I think that's okay here -- the original poster asked for a definition of equivalence, not for a definition that was always decidable.