There are problems in physics that are undecidable, even if you have all the initial information about the physical system.

"In math and computer science, researchers have long understood that some questions are fundamentally unanswerable. Now physicists are exploring how even ordinary physical systems put hard limits on what we can predict, even in principle."

https://www.quantamagazine.org/next-level-chaos-traces-the-true-limit-of-predictability-20250307/

#Physics #Computation #HaltingProblem

Collatzeral Damage: Bitwise and Proof Foolish

Let’s talk about the Collatz Conjecture, which is like mathematicians’ original version of this programmer joke:

The Collatz conjecture is an infamous trap for the young and ambitious. Despite its simple construction, it has evaded proofs and general solutions for nearly a century. Veritasium made a video about this conjecture, which I recommend:

https://www.youtube.com/watch?v=094y1Z2wpJg

The Collatz conjecture involves a recursive function that contains one branch: If a number is odd, multiply it by 3 then add 1. If it is even, divide it by 2.

The conjecture states that repeating this operation will eventually reach 1 for all positive integers.

Quick observation:

• Even numbers take you closer to your goal of reaching your goal (reaching 0).
• Odd numbers take you further away from your goal.

You can write recursive code that implements the Collatz function like so:

function collatz(num) {  console.log(num);  if (num === 1) {    return;  }  return (num % 2 === 1)     ? collatz((3 * num) + 1)    : collatz(num >> 1);}

If the Collatz conjecture is false, there is some integer for which the return statement will never be reached.

We don’t know if the conjecture is true or not.

We do know that it has held up for a hell of a lot of positive integers (from a human perspective), and have yet to find a counterexample, but we don’t know if it’s necessarily true for all positive integers.

What if there’s actually a cycle somewhere (similar to what I discussed in the context of hash functions)?

That mathematicians don’t know the answer isn’t really interesting for the readers of this blog, but why the answer is so elusive (despite the intuitive simple construction of the function central to the Collatz conjecture) is something I think we can say something interesting about.

But first, let’s talk about a class of cryptographic algorithm that serves as the building block for several types of hash functions and stream ciphers used across the Internet today.

Important

I am taking a lot of liberties in this blog post, and I am prioritizing clarity over technical precision.

Readers will be better served by cross-referencing this entertainment-focused blog post with the work of actual mathematicians.

And for the pedants in the audience: if something seems imprecise, it’s probably because I made a trade-off to help a wider audience gain a basic intuition.

Add, Rotate, XOR (ARX)

ARX is a category of cryptography algorithms that is used to build various cryptography building blocks. The SHA-2 family of hash functions and the ChaCha stream cipher both an ARX construction (and both are used in a lot of Internet traffic).

Let’s focus on ChaCha for the moment, focusing on the reference implementation that ships with libsodium:

#define U32C(v) (v##U)#define U32V(v) ((uint32_t)(v) &U32C(0xFFFFFFFF))#define ROTATE(v, c) (ROTL32(v, c))#define XOR(v, w) ((v) ^ (w))#define PLUS(v, w) (U32V((v) + (w)))#define PLUSONE(v) (PLUS((v), 1))#define QUARTERROUND(a, b, c, d) \    a = PLUS(a, b);              \    d = ROTATE(XOR(d, a), 16);   \    c = PLUS(c, d);              \    b = ROTATE(XOR(b, c), 12);   \    a = PLUS(a, b);              \    d = ROTATE(XOR(d, a), 8);    \    c = PLUS(c, d);              \    b = ROTATE(XOR(b, c), 7);

At the core of ChaCha is the quarter round function. This is applied on alternating columns and diagonals of the input state until the desired number of rounds has been completed.

for (i = 20; i > 0; i -= 2) {    QUARTERROUND(x0, x4, x8, x12)    QUARTERROUND(x1, x5, x9, x13)    QUARTERROUND(x2, x6, x10, x14)    QUARTERROUND(x3, x7, x11, x15)    QUARTERROUND(x0, x5, x10, x15)    QUARTERROUND(x1, x6, x11, x12)    QUARTERROUND(x2, x7, x8, x13)    QUARTERROUND(x3, x4, x9, x14)}

After all rounds are complete, the initial state is added to the output. This 512-bit state includes the key (which consists of up to 256 bits), nonce, and some constant values. Because half of the input bytes are your secret key, an attacker without knowledge of the key cannot invert the calculation.

ChaCha is an improvement of another stream cipher from the same family as the eSTREAM finalist, Salsa20. ChaCha improved the diffusion per round and performance. This makes ChaCha less susceptible to cryptanalysis, even in extremely reduced-round variants (e.g., ChaCha8 vs ChaCha20).

As interesting as all that is, the important bits to know is that the ChaCha update emphasized improving diffusion.

What does that mean, exactly?

What is Diffusion?

Diffusion is a measurement of how much the output state changes when each bit differs in the input state.

This is important for making it difficult to statistically analyze the relationship between the input and outputs of a cryptographic function.

ARX Diffusion

ARX consists of three operations: Rotation (sliding bits around like a flywheel), addition, and eXclusive OR (also known as XOR).

Comparing Salsa20 and ChaCha’s quarter round, using the notation from the source code on Wikipedia, you see:

Salsa20 Quarter Round

b ^= (a + d) <<<  7;c ^= (b + a) <<<  9;d ^= (c + b) <<< 13;a ^= (d + c) <<< 18;

Addition then rotation then XOR.

ChaCha Quarter Round

a += b; d ^= a; d <<<= 16;c += d; b ^= c; b <<<= 12;a += b; d ^= a; d <<<=  8;c += d; b ^= c; b <<<=  7;

Addition then XOR then rotation.

Each step of the quarter round function still involves addition, rotation, and XOR, but their usage is different. (Also, they just update values directly rather than involving an extra temporary value to implicitly occupy a stack register.)

And it’s subtle, but if you play with these different quarter rounds with slightly different inputs, you can see how the diffusion is improved with the second construction in fewer numbers of rounds.

“Why does diffusion matter?”

Bit diffusion in ARX constructions is one of the ways that ciphers ensure their output remains indistinguishable from a random oracle.

If you’ve ever looked at a cryptographic hash function before, or heard about the “avalanche effect“, that’s precisely what we want out of these ARX constructions.

“So what?”

As some of you might remember from your studies, XOR is just addition without carry (mod 2).

If you repeat your same experimentation but only use one operation (AR or RX), you’ll find that your diffusion is poor.

This is because addition is an abstraction that hides a very important feature that’s often taken for granted.

Carry Propagation

Let’s say, for a learning exercise, you wanted to build integer addition entirely out of bitwise operators: AND, OR, NOT, XOR, and the left and right bit shift operators.

As already mentioned above, XOR is just addition without carry. So that part’s easy:

def add_bits_no_carry(x, y):    return x ^ y

How about carrying values to the next place? Well, consider the following table:

That third column sure looks like an “AND” operator, does it not?

Great, but what if you had a carry value from the previous step?

Well, now you have to implement two half-adders: One to handle the input carry value with one input, and the other to handle the other input and produce the next output carry value.

def half_adder(x, y):    return [x ^ y, x & y]def add_bits(x, y, c_in):    [a, b] = half_adder(x, y)    [d, e] = half_adder(a, c_in)    return [d, b ^ e]

If you feel lost, this hardware tutorial explains it with diagrams.

The main thing I want you to take away is that addition is much more complicated than XOR because of carry propagation.

On Computation and Information Theory

We use XOR to mix data (which could be plaintext, or could be all zeroes) with pseudo-random bytes, since it’s perfectly hiding so long as the bytes we’re mixing them with is unknown. This is the intuition underlying one-time pads and modern stream ciphers (including the ones we’re discussing).

In the context of ARX, because some operations (addition) propagate carries and others don’t (XOR), when you combine these steps with rotating the bits in-place, it becomes very easy to mix the output bits in a short number of rounds of operations. Cryptographers measure how well bits are mixed across a large number of inputs and reject designs that don’t perform well (generally speaking).

But a direct consequence of the hidden complexity of addition with carry is that the state you’re operating within is larger than the output. This means that some information is used (carried over from previous bits or limbs) that is not revealed directly in the output bit(s).

It’s easy to add two numbers together, but if you don’t know either of the numbers, it’s impossible to know the other (unless, of course, a side-channel leaks enough information to deduce one of them).

“That’s neat and all, but what does it imply?”

Don’t worry, I’m going somewhere with this.

Turing the Page

Let’s briefly talk about Turing machines.

The relevant Wikipedia article covers them adequately well. For everyone else, another Veritasium video:

https://www.youtube.com/watch?v=HeQX2HjkcNo

A Turing machine is a mathematical model for computation.

The basic idea is that you have a tape of symbols, a head that reads from the tape, and an internal state that determines the next move.

We don’t need too formal of a treatment here. I’m not exactly trying to prove the halting problem is undecidable.

A dumb joke I like to tell my computer science friends:

I’ve solved the Halting problem! It’s called: “the heat death of the universe,” at which point the program fucking halts!

But do put a pin in this, because it will come up towards the end.

Bitwise Collatz Functions

Above, I wrote a bit of code that implements the Collatz function, but I was a bit lazy about it.

In truth, you don’t need multiplication or the modulo operator. You can, instead, use bitwise operations and one addition.

• The modulo 2 check can be replaced by a bitwise AND mask with 1. Odd values will return 1, even will return 0.
• When the least significant bit is 0:
  Dividing by 2 is the same as right-shifting by 1.
• When the least significant bit is 1:
  Multiplying by 3 then adding 1 can be rewritten as the following steps:
  • Left shift by 1 (2n)
  • Set the lower bit to 1 (+1), using bitwise OR
  • Add the original number (+n)

Thus, our function instead looks like:

function collatz(num) {  console.log(num);  if (num === 1) {    return;  }  return (num & 1)    ? collatz(((num << 1) | 1) + num)    : collatz(num >> 1);}

That is to say, you can implement most of the Collatz function with bitwise operators, and only need one addition (with carries) in the end.

Suddenly, the discussion above about carry propagation might seem a lot more relevant!

Small Example

Imagine you encode a number as a binary string. For example, 257.

When you work through the algorithm sketched out above, you end up doing this:

       n == 0001_0000_0001     2*n == 0010_0000_0010 # left shift by 1 2*n + 1 == 0010_0000_0011 # bitwise OR with 1       add: 0001_0000_0001 # n            0010_0000_0011 # 2n + 1            # This is where carry propagation comes in!    result: 0011_0000_0100

When you perform the 3n+1 branch of the Collatz function the way I constructed it, that last addition of n will propagate carries.

And that carry propagation is where the trouble starts.

Since the (3n+1) branch is only ever invoked with odd values for n, you can guarantee that the next step will be followed by at least one division by 2 (since 3n+1 is even for any odd n).

This allows you look ahead two steps at a time, but there is no easy way to predict how many back-to-back (3n+1)/2 two-steps you will encounter from a given value. Instead, you have to actually perform the calculation and see what happens.

Collatz Machines

The input and output of the Collatz function is an integer of arbitrary size. The behavior branches depending on the least significant bit of the input.

You can think of the least significant bit as the “head” of a machine similar to a Turing machine.

However, instead of moving the head along a tape, the Collatz function does one of two things:

1. Moves the symbols on the tape one space to the right (somewhat familiar territory for Turing Machines).
2. Rewrites all of the symbols on the tape to the left of the head, according to some algorithm. This algorithm makes the tape longer.

As we observed previously, the carry propagation implicit to addition makes the bits diffuse in a way that’s hard to generalize faster than simply performing the addition and seeing what results from it.

Proving that this Collatz machine halts for all positive inputs would also prove the Collatz Conjecture. But as we saw with proper Turing Machines, this might not be possible.

Pedants on the /r/math subreddit were quick to point out that this isn’t necessarily true, but the goal of this blog post was not to state a technically precise truth, but to explore the Collatz conjecture from a different angle.

The important disclaimer at the top isn’t some cop-out boilerplate I slap on everything I write to absolve me of any retribution for my mistakes. It’s actually important for everyone to read and understand it.

The entire point of this blog is “hey, here’s a neat idea to think about” not “here’s a universal truth about mathematics I discovered”. For that, I would have written an actual paper, not a furry blog. Unfortunately, I have no new insights to offer on anything, nor will I probably ever.

I recommend reading the comment I linked at the start of this quoted section, as it’s grounded in a more formal mathematics understanding than this blog post.

Is It Unsolvable?

With all this in mind, in the general case, the Collatz Conjecture may very well one day prove to be as undecidable as the Halting Problem.

Or, maybe someone will find a cycle within the integer space that fails to ever reach 1.

As it stands right now, there have been a lot of interesting approaches to try to solve it. The first Veritasium video linked above talked about some of these ideas.

Maybe we need new mathematic tools first. Or perhaps the Langlands project will uncover a relationship between unrelated areas of mathematical research that already exist today that will yield an answer to this nearly century-old conjecture.

Either way, I hope you find this topic… mildly interesting. Enough to appreciate the problem, not so much that you think you can solve it yourself.

Stay safe, don’t drink and derive, and happy hacking.

Header art: AJ and CMYKat.

#CollatzConjecture #define #HaltingProblem #mathematics #TuringMachines

#Politics has a #haltingProblem.  You can try to build logical systems of law and administration but you cannot predict the outcome of your logic.  The more logical, sensible, and reasonable your system design, the more likely you are to have to turn it off and on again, and it is important to build that option in, as a permanent feature outside the logic of the system.

To Halt or Not to Halt? That Is the Question by Cristian Calude, 2024

Can mathematics be done by computers only? Can software testing be fully automated? Can you write an anti-virus program which never needs any updates? Can we make the Internet perfectly secure? Your guess is correct: the answer to each question is negative.

@bookstodon
#books
#nonfiction
#computing
#algorithms
#HaltingProblem

@aragubas Get ready for a computer science info dump.

What @crumbcake described in his last reply is the halting problem, which is undecidable. In other words, it's impossible for a computer (as we currently define them) to answer that problem for every possible input. Computerphile did a 6 minute video explaining the halting problem and why it's undecidable if you'd like to know more.

The question of P vs NP is, informally stated, this: If it's easy to check an answer to a problem, is it also easy to find an answer? An example of such a problem is sudoku. It's pretty easy to look over a completed grid for correctness but it seems much harder to find a solution to an incomplete grid. But is it harder under the more rigorous computer science definitions of computational complexity? We actually don't know, and there's a million dollar prize if you can prove it one way or the other.

If you'd like to learn a little more, I'd highly recommend this 11 minute long video about the computational complexity zoo for a relatively approachable introduction to all these concepts. Enjoy. 💙

#ComputerScience #PvsNP #HaltingProblem #ComputationalComplexity

Today I learned that Magic: The Gathering is Turing complete. 🤯 https://arxiv.org/abs/1904.09828

#MagicTheGathering #MTG #TuringComplete #HaltingProblem

My favourite bits of the conclusion are that optimally playing MtG is at least of order 0(omega) (lol), and that you *could* in fact force a solve of the halting problem in a real tournament. If I still played, this would quickly become my life goal 😂😂 #MtG #HaltingProblem #Phyrexia

I learnt this while having lunch with my technical team, and I realised that none of them were so deep into computer science to get how awesome this is 🥲 sooooo hopefully there are computational complexity peeps out there that can go “omg wow” with me 😃 #MtG #HaltingProblem #Phyrexia

Omg. Someone has proved that Magic the Gathering is Turing Undecidable, as you can create #MtG games of forced moves that solve the #HaltingProblem. This is of course impossible, meaning that the end state of a game *with totally deterministic, forced moves* is indeterminable by computation.

In the literature, that makes MtG the most computationally hard game known. This should explain why #Phyrexia never won, cause machines can’t predict how a battle between planeswalkers will play out :P

https://arxiv.org/abs/1904.09828

Fernando Rosas (unfortunately not on Mastodon) asked on bsky:

"Has anyone figured out what exactly is the relation between the ideas of feedback, recurrence, and self-reference?"

A really interesting question.

He pointed to this paper for ideas: https://arxiv.org/abs/1711.02456
"Self-referential basis of undecidable dynamics: from The Liar Paradox and The Halting Problem to The Edge of Chaos"

I did some desk research and found this cool paper:
https://arxiv.org/abs/1112.2141
"Resolving Gödel's Incompleteness Myth: Polynomial Equations and Dynamical Systems for Algebraic Logic"
that argues there is no essential incompleteness in formal reasoning systems if you look closely enough (using a more elaborate formalism based on polynomial equations to represent and evaluate logical proposition).

I wonder if analogous construction could be created for related theorems like the halting problem in computability theory.

#DynamicalSystems #IncompletenessTheorem #PolynomialEquations #HaltingProblem #Undecidability #SelfReference #Recurrence

@aardrian @alastc I believe your last point has a challenge, see #haltingproblem

Check out this brand new video from ACCU 2023!

Lightning Talk: The Halting Problem & Alan Turing – by @MatRopert – ACCU 2023

https://www.youtube.com/watch?v=RtLHYhBXQL0

#coding #haltingproblem #mathematics #programming #softwareengineering #turing

#Poem by Geoffrey K. Pullum that explains the #HaltingProblem:

http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html

another case of stopping quite early vs letting it run

#generativeart #abstractart #digitalart #haltingproblem

generative art version of the halting problem: it is generally impossible to determine if letting an algorithm continue will produce a better or worse artwork #generativeart #abstractart #digitalart #haltingproblem

The second version sounds a bit more like the German poem "Der #Erlkönig". While the end is like this German apple poem (which consists only of the word apple). But it's kind of fascinating, that #ChatGPT decided to add a loop in the end to avoid the song to stop. As if ChatGPT thought, "ha, I'll just add a #HaltingProblem, no one will be able to prove or disprove then that this song is ending..." #monkeyisland #apirateiwasmenttobe

HUGE NEWS in #computerscience #haltingproblem SOLVED
why is no one talking about this?

if going_to_halt {
nuh.uh()
} else {
// extra space for activities :3
}

How This One Question Breaks Computers - by Up and Atom:

https://farside.link/https://www.youtube.com/watch?v=sG0obNcgNJM
(or YT: https://www.youtube.com/watch?v=sG0obNcgNJM)

Such a great and creative explanation! ✨

You'll love it!

When viewing this related to modern #AI promises, we really should be more #humble.

#Computing #Math #mathematics #HaltingProblem #Turing #Entscheidungsproblem

#turing #haltingproblem #computeers #Godel https://youtu.be/sG0obNcgNJM