Puppet Master

Ω is my own personal favorite transcendental number. Ω isn't really a specific number, but rather a family of related numbers with bizzare properties. It's the one real transcendental number that I know of that comes from the theory of computation, that is important, and that expresses meaningful fundamental mathematical properties. It's also deeply non-computable; meaning that not only is it non-computable, but even computing meta-information about it is non-computable. And yet, it's almost computable. It's just all around awfully cool.

So. What is it Ω?

It's sometimes called the halting probability. The idea of it is that it encodes the probability that a given infinitely long random bit string contains a prefix that represents a halting program.

It's a strange notion, and I'm going to take a few paragraphs to try to elaborate on what that means, before I go into detail about how the number is generated, and what sorts of bizzare properties it has.

Remember that in the theory of computation, one of the most fundamental results is the non-computability of the halting problem. The halting problem is the question "Given a program P and input I, if I run P on I, will it ever stop?" You cannot write a program that reads P and I and gives you the answer to the halting problem. It's impossible. And what's more, the statement that the halting problem is not computable is actually equivalent to the fundamental statement of Gödel's incompleteness theorem.

Ω is something related to the halting problem, but stranger. The fundamental question of Ω is: if you hand me a string of 0s and 1s, and I'm allowed to look at it one bit at a time, what's the probability that eventually the part that I've seen will be a program that eventually stops?

When you look at this definition, your reaction should be "Huh? Who cares?"

The catch is that this number - this probability - is a number which is easy to define; it's not computable; it's completely uncompressible; it's normal.

Let's take a moment and look at those properties:
Non-computable: no program can compute Ω. In fact, beyond a certain value N (which is non-computable!), you cannot compute the value of any bit of Ω.
Uncompressible: there is no way to represent Ω in a non-infinite way; in fact, there is no way to represent any substring of Ω in less bits than there are in that substring.
Normal: the digits of Ω are completely random and unpatterned; the value of and digit in Ω is equally likely to be a zero or a one; any selected pair of digits is equally likely to be any of the 4 possibilities 00, 01, 10, 100; and so on.

So, now we know a little bit about why Ω is so strange, but we still haven't really defined it precisely. What is Ω? How does it get these bizzare properties?

Well, as I said at the beginning, Ω isn't a single number; it's a family of numbers. The value of an Ω is based on two things: an effective (that is, turing equivalent) computing device; and a prefix-free encoding of programs for that computing device as strings of bits.

(The prefix-free bit is important, and it's also probably not familiar to most people, so let's take a moment to define it. A prefix-free encoding is an encoding where for any given string which is valid in the encoding, no prefix of that string is a valid string in the encoding. If you're familiar with data compression, Huffman codes are a common example of a prefix-free encoding.)

So let's assume we have a computing device, which we'll call φ. We'll write the result of running φ on a program encoding as the binary number p as &phi(p). And let's assume that we've set up φ so that it only accepts programs in a prefix-free encoding, which we'll call ε; and the set of programs coded in ε, we'll call Ε; and we'll write φ(p)↓ to mean φ(p) halts. Then we can define Ω as:

Ωφ,ε = Σp ∈ Ε|p↓ 2-len(p)

So: for each program in our prefix-free encoding, if it halts, we add 2-length(p) to Ω.

Ω is an incredibly odd number. As I said before, it's random, uncompressible, and has a fully normal distribution of digits.

But where it gets fascinatingly bizzare is when you start considering its computability properties.

Ω is definable. We can (and have) provided a specific, precise definition of it. We've even described a procedure by which you can conceptually generate it. But despite that, it's deeply uncomputable. There are procedures where we can compute a finite prefix of it. But there's a limit: there's a point beyond which we cannot compute any digits of it. And there is no way to compute that point. So, for example, there's a very interesting paper where the authors computed the value of Ω for a Minsky machine; they were able to compute 84 bits of it; but the last 20 are unreliable, because it's uncertain whether or not they're actually beyond the limit, and so they may be wrong. But we can't tell!

What does Ω mean? It's actually something quite meaningful. It's a number that encodes some of the very deepest information about what it's possible to compute. It gives a way to measure the probability of computability. In a very real sense, it represents the overall nature and structure of computability in terms of a discrete probability. It's an amazingly dense container of information - as a n infinitely long number and so thoroughly non-compressible, it contains an unmeasurable quantity of information. And we can't get near most of it!

No comments

The Architect vs Neo transcript

Friday, 4. August 2006, 01:46:09

From The Matrix Reloaded.........
----------------------------------

The Architect - Hello, Neo.

Neo - Who are you?

The Architect - I am the Architect. I created the matrix. I've been waiting for you. You have many questions, and although the process has altered your consciousness, you remain irrevocably human. Ergo, some of my answers you will understand, and some of them you will not. Concordantly, while your first question may be the most pertinent, you may or may not realize it is also irrelevant.

Neo - Why am I here?

The Architect - Your life is the sum of a remainder of an unbalanced equation inherent to the programming of the matrix. You are the eventuality of an anomaly, which despite my sincerest efforts I have been unable to eliminate from what is otherwise a harmony of mathematical precision. While it remains a burden to sedulously avoid it, it is not unexpected, and thus not beyond a measure of control. Which has led you, inexorably, here.

Neo - You haven't answered my question.

The Architect - Quite right. Interesting. That was quicker than the others.

*The responses of the other Ones appear on the monitors: "Others? What others? How many? Answer me!"*

The Architect - The matrix is older than you know. I prefer counting from the emergence of one integral anomaly to the emergence of the next, in which case this is the sixth version.

*Again, the responses of the other Ones appear on the monitors: "Five versions? Three? I've been lied too. This is bullshit."*

Neo: There are only two possible explanations: either no one told me, or no one knows.

The Architect - Precisely. As you are undoubtedly gathering, the anomaly's systemic, creating fluctuations in even the most simplistic equations.

*Once again, the responses of the other Ones appear on the monitors: "You can't control me! F*ck you! I'm going to kill you! You can't make me do anything!*

Neo - Choice. The problem is choice.

*The scene cuts to Trinity fighting an agent, and then back to the Architect's room*

The Architect - The first matrix I designed was quite naturally perfect, it was a work of art, flawless, sublime. A triumph equaled only by its monumental failure. The inevitability of its doom is as apparent to me now as a consequence of the imperfection inherent in every human being, thus I redesigned it based on your history to more accurately reflect the varying grotesqueries of your nature. However, I was again frustrated by failure. I have since come to understand that the answer eluded me because it required a lesser mind, or perhaps a mind less bound by the parameters of perfection. Thus, the answer was stumbled upon by another, an intuitive program, initially created to investigate certain aspects of the human psyche. If I am the father of the matrix, she would undoubtedly be its mother.

Neo - The Oracle.

The Architect - Please. As I was saying, she stumbled upon a solution whereby nearly 99.9% of all test subjects accepted the program, as long as they were given a choice, even if they were only aware of the choice at a near unconscious level. While this answer functioned, it was obviously fundamentally flawed, thus creating the otherwise contradictory systemic anomaly, that if left unchecked might threaten the system itself. Ergo, those that refused the program, while a minority, if unchecked, would constitute an escalating probability of disaster.

Neo - This is about Zion.

The Architect - You are here because Zion is about to be destroyed. Its every living inhabitant terminated, its entire existence eradicated.

Neo - Bullshit.

*The responses of the other Ones appear on the monitors: "Bullshit!"*

The Architect - Denial is the most predictable of all human responses. But, rest assured, this will be the sixth time we have destroyed it, and we have become exceedingly efficient at it.

*Scene cuts to Trinity fighting an agent, and then back to the Architects room.*

The Architect - The function of the One is now to return to the source, allowing a temporary dissemination of the code you carry, reinserting the prime program. After which you will be required to select from the matrix 23 individuals, 16 female, 7 male, to rebuild Zion. Failure to comply with this process will result in a cataclysmic system crash killing everyone connected to the matrix, which coupled with the extermination of Zion will ultimately result in the extinction of the entire human race.

Neo - You won't let it happen, you can't. You need human beings to survive.

The Architect - There are levels of survival we are prepared to accept. However, the relevant issue is whether or not you are ready to accept the responsibility for the death of every human being in this world.

*The Architect presses a button on a pen that he is holding, and images of people from all over the matrix appear on the monitors*

The Architect - It is interesting reading your reactions. Your five predecessors were by design based on a similar predication, a contingent affirmation that was meant to create a profound attachment to the rest of your species, facilitating the function of the one. While the others experienced this in a very general way, your experience is far more specific. Vis-a-vis, love.

*Images of Trinity fighting the agent from Neo's dream appear on the monitors*

Neo - Trinity.

The Architect - Apropos, she entered the matrix to save your life at the cost of her own.

Neo - No!

The Architect - Which brings us at last to the moment of truth, wherein the fundamental flaw is ultimately expressed, and the anomaly revealed as both beginning, and end. There are two doors. The door to your right leads to the source, and the salvation of Zion. The door to the left leads back to the matrix, to her, and to the end of your species. As you adequately put, the problem is choice. But we already know what you're going to do, don't we? Already I can see the chain reaction, the chemical precursors that signal the onset of emotion, designed specifically to overwhelm logic, and reason. An emotion that is already blinding you from the simple, and obvious truth: she is going to die, and there is nothing that you can do to stop it.

*Neo walks to the door on his left*

The Architect - Humph. Hope, it is the quintessential human delusion, simultaneously the source of your greatest strength, and your greatest weakness.

Neo - If I were you, I would hope that we don't meet again.

The Architect - We won't.

No comments

scatterchat

Tuesday, 1. August 2006, 02:37:42

ScatterChat is a HACKTIVIST WEAPON designed to allow non-technical human rights activists and political dissidents to communicate securely and anonymously while operating in hostile territory. It is also useful in corporate settings, or in other situations where privacy is desired.

It is a secure instant messaging client (based upon the Gaim software) that provides end-to-end encryption, integrated onion-routing with Tor, secure file transfers, and easy-to-read documentation.

Its security features include resiliency against partial compromise through perfect forward secrecy, immunity from replay attacks, and limited resistance to traffic analysis... all reinforced through a pro-actively secure design.

2 comments

tar2mo tips

Wednesday, 19. July 2006, 15:22:35

// How to modify Slax without using Slax
//
// by kn1ghtl0rd@hotmail.com
//
// www.phreakshow.info

During the process of modifying the Slax linux live cd for our own purpose of
creating Podcast Fertilizer I came up with a problem. I had to use Slax to
modify it. This is pretty inconvienent because you either have to use an
emulator and modify the module then save it to a disk or flash drive, or you
have to burn a cd and do the same thing. I wanted to be able to use the module
editing tools that came with the Slax distro without needing Slax.

On the Slax.ISO there is a folder called tools that holds programs to unpack a
module and repack it. It allows you to convert directories to modules, .tar
files to modules, and modules to directories. The modules are encoded with the
squash file system, which is also contained in that folder.

The first step to using the tools is to copy all the files from the tools
directory into /usr/lib/ directory. The next step is to do chmod 777 on all the
module conversion .sh scripts. Once all the scripts are ready you need to edit
the liblinuxlive file. Search the file for a line that looks like this:

create_module()
{
mksquashfs "$1" "$2" $3 >/dev/null
if [ $? -ne 0 ]; then return 1; fi
chmod oga-x "$2" # remove execute attrib
}

You must change it to look like this:

create_module()
{
./mksquashfs "$1" "$2" $3 >/dev/null
if [ $? -ne 0 ]; then return 1; fi
chmod oga-x "$2" # remove execute attrib
}

This will allow you to run the dir2mo or tar2mo commands without getting an
error. All the commands need to be ran under root, so keep that in mind.

That should be all there is to it. The commands work the same as they would in
Slax. The syntax is basically dir2mo /directory/ modulesavename.mo. Reverse it
for the mo2dir. If you have any problems you can email me or join #infonomicon
on irc.freenode.net and ask me in there.

No comments

Slackware + Zenwalk

Thursday, 13. July 2006, 01:16:56

This is a nice interview about Zenwalk:

http://www.free-bees.co.uk/articles/zenwalkinterview/

-Slax2501

No comments

Ringtones for free!!!

Sunday, 2. July 2006, 13:53:50

This is easy to do. Just follow the instructions.
-2501

--------

DSL DIY Free Ringtones
No need to pay for ringtones when you could make them for free
How to make free ringtones using DSL

Here is what you need first:
1) Grab Audacity.dsl from the MyDSL repository.
(under multimedia)

2) Grab Lame.dsl from the MyDSL repository.
(also under multimedia)

3) Grab your favorite song in mp3 format.
(you know where to get it)

Once you have all that Launch Audacity; from your menu MyDSL -> Audacity.
After a moment or two you should have an application that looks like this:

Next open your song up in Audacity by clicking File -> Open, then selecting your choice mp3. Audacity will have to convert your mp3 into its native format. This could take a few moments. After it is done and the song is fully loaded Audacity should look something like this:

At this point you may want to play your song in Audacity to see what part of the song you want to have for your ringtone. Once you figure that part out, selecting the part of the song that you want to sample is simple. Just use your mouse to highlight the section you want.

In this screenshot I chose the beginning of the song, but you could have chosen the middle or the end just as easily.

Be sure to play the selected area so that you know that you have the right snippet for your ringtone.

Once you have the piece you like, go to Edit -> Copy to get the song snippet, then go to File -> New to launch a new Audacity window. Once the new window is open go to it and select Edit -> Paste. You now have the sampled song snippet in the new Audacity window. Half way there! Well, almost.

This screenshot is the 15 second song sample I selected. As you can see, the 15 second clip is represented in the same amount of space which causes us to have a more detailed view of the music without zooming. Notice that at the beginning of the song there is no sound, we could remove that section by selecting it with the mouse and do a Edit -> Delete. On the tail end of your music sample you may want to have the song fade out. In the photo I selected the last second and a half or so and I chose Effect -> Fade out. You can visually see the music tapering down. There are lots of effects in Audacity, but I like to keep it simple.

At this point we are dun with the editing. You should listen to the sample now and see if you like what you hear. If you do, then lets keep on going.

We are going to use Lame to do the mp3 encoding, so we will export this sample as an uncompressed .wav. In Audacity, select File -> Export as Wav. I saved mine as sample.wav.

We're all done with Audacity, now it is time to use Lame. Lame is a command line tool, so you will be using Aterm to issues the mp3 encoding commands to lame.

According to what I've read one could use 16, 24 or 32 bit rate while encoding. Most recommend not using 16 bit rate because it gives poor sound quality. On the other hand 32 bit encoding makes a much larger file. A good middle of the road approach is to use 24 bit format which makes an mp3 about 25% smaller than a 32 bit file yet still has good sound quality. On good speakers you certainly could hear the difference between 24 and 32, bot on your tiny cell phone speakers it won't make any difference.

To encode the mp3 all you have to do is: dsl@box:~$ lame -b

I chose 24 bit encoding and medium to make for a smaller file. For my wav file I gave this command:
dsl@box:~$ lame -b 24 sample.wav sample.mp3

Done! See how simple that is? Now, to get it to your phone on from DSL you have a few options:
1 Email your new ringtone to your phone
2 If your phone has USB support, plug it in and move the .mp3 over
3 Bluetooth, well, you could save it onto a drive and access that drove
from an OS that does Bluetooth later. We are only a 50MB distribution after all!

No comments

« Prev 1 ... 9 10 11 12 13 14 15 Next »

Showing posts 131 - 140 of 143.