Cryptography-Digest Digest #933, Volume #8 Tue, 19 Jan 99 22:13:03 EST
Contents:
Re: Visual Basic Cipher ("Oliver Keeling")
Re: Metaphysics Of Randomness (Darren New)
Re: interview (Mr. Tines)
Re: Trying to find simple, yet effective implementation of crypto... (Mr. Tines)
Re: Metaphysics Of Randomness (Darren New)
Re: Metaphysics Of Randomness (R. Knauer)
Re: Metaphysics Of Randomness (R. Knauer)
Re: Metaphysics Of Randomness (Darren New)
Re: Metaphysics Of Randomness (R. Knauer)
----------------------------------------------------------------------------
From: "Oliver Keeling" <[EMAIL PROTECTED]>
Subject: Re: Visual Basic Cipher
Date: Tue, 19 Jan 1999 22:10:55 GMT
Following on this thread - I came across the following in a VB news group.
I haven't had the time yet to look at it in any detail but it seems to be
XOR based - dunno how secure it is either, but it seems to work quite fast.
There are some problems though - it seems to struggle with de-coding large
string (it encodes OK) but drops short on the de-code. I put a 196Kb file
through it and it encrypted it in a second or two (not lightening fast I
know) but better than anything else I have tried in VB. But when I tried to
decrypt it - it only de-crypted the first 20 lines or so. This I think is
in part coz VB seems to take ASCII 26 to be the end of file marker so
using -
do while not eof(1)
leads to problems!!
Anyway - hope this helps and maybe some of the cryptanalists out there may
be able to pass comment on how secure it is.
Olly
Option Explicit
Function StrEncode(ByVal s As String, key As Long, salt As Boolean) As
String
Dim n As Long, i As Long, ss As String
Dim k1 As Long, k2 As Long, k3 As Long, k4 As Long, t As Long
Static saltvalue As String * 4
If salt Then
For i = 1 To 4
t = 100 * (1 + Asc(Mid(saltvalue, i, 1))) * Rnd() * (Timer + 1)
Mid(saltvalue, i, 1) = Chr(t Mod 256)
Next
s = Mid(saltvalue, 1, 2) & s & Mid(saltvalue, 3, 2)
End If
n = Len(s)
ss = Space(n)
ReDim sn(n) As Long
k1 = 11 + (key Mod 233): k2 = 7 + (key Mod 239)
k3 = 5 + (key Mod 241): k4 = 3 + (key Mod 251)
For i = 1 To n: sn(i) = Asc(Mid(s, i, 1)): Next i
For i = 2 To n: sn(i) = sn(i) Xor sn(i - 1) Xor ((k1 * sn(i - 1)) Mod 256):
Next
For i = n - 1 To 1 Step -1: sn(i) = sn(i) Xor sn(i + 1) Xor (k2 * sn(i + 1))
Mod 256: Next
For i = 3 To n: sn(i) = sn(i) Xor sn(i - 2) Xor (k3 * sn(i - 1)) Mod 256:
Next
For i = n - 2 To 1 Step -1: sn(i) = sn(i) Xor sn(i + 2) Xor (k4 * sn(i + 1))
Mod 256: Next
For i = 1 To n: Mid(ss, i, 1) = Chr(sn(i)): Next i
StrEncode = ss
saltvalue = Mid(ss, Len(ss) / 2, 4)
End Function
Function StrDecode(ByVal s As String, key As Long, salt As Boolean) As
String
Dim n As Long, i As Long, ss As String
Dim k1 As Long, k2 As Long, k3 As Long, k4 As Long
n = Len(s)
ss = Space(n)
ReDim sn(n) As Long
k1 = 11 + (key Mod 233): k2 = 7 + (key Mod 239)
k3 = 5 + (key Mod 241): k4 = 3 + (key Mod 251)
For i = 1 To n: sn(i) = Asc(Mid(s, i, 1)): Next
For i = 1 To n - 2: sn(i) = sn(i) Xor sn(i + 2) Xor (k4 * sn(i + 1)) Mod
256: Next
For i = n To 3 Step -1: sn(i) = sn(i) Xor sn(i - 2) Xor (k3 * sn(i - 1)) Mod
256: Next
For i = 1 To n - 1: sn(i) = sn(i) Xor sn(i + 1) Xor (k2 * sn(i + 1)) Mod
256: Next
For i = n To 2 Step -1: sn(i) = sn(i) Xor sn(i - 1) Xor (k1 * sn(i - 1)) Mod
256: Next
For i = 1 To n: Mid(ss, i, 1) = Chr(sn(i)): Next i
If salt Then StrDecode = Mid(ss, 3, Len(ss) - 4) Else StrDecode = ss
End Function
'Private Sub cmdDecrypt_Click()
'Dim key As Long
'Dim salt As Boolean
'Dim s As String, ss As String
'key = 1234567890 'Or any other postive integer
'salt = False
's = txt.Text
'ss = StrDecode(s, key, salt)
'txt.Text = ss
'End Sub
'Private Sub cmdEncrypt_Click()
'Dim key As Long
'Dim salt As Boolean
'Dim s As String, ss As String
'key = 1234567890 'Or any other postive integer
'salt = False
's = txt.Text
'ss = StrEncode(s, key, salt)
'txt.Text = ss
'End Sub
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Date: Tue, 19 Jan 1999 21:52:53 GMT
> Yes but calculating could take a very long time if the complexity of your
> algorithm is too great. See [1] for details.
These are turing machines. You have all the time in the world. ;-)
If you start worrying about the *efficiency* of your turing machines, or
their speed, you have to start worrying about how long that infinite
tape is going to get, too. :-)
--
Darren New / Senior Software Architect / MessageMedia, Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"You could even do it in C++, though that should only be done
by folks who think that self-flagellation is for the effete."
------------------------------
From: Mr. Tines <[EMAIL PROTECTED]>
Subject: Re: interview
Date: 19 Jan 1999 20:27 +0000
###
On 19 Jan 1999 00:56:37 GMT, in <01be4345$57776740$0acdc8d0@computer-liebe>
"Phred Dobbs (take out the q to email me)" <[EMAIL PROTECTED]>
wrote.....
> I am a senior in High School and I am taking an independent study
> mentorship
> class in Cryptography. I am looking for people in the cryptography field
to
> interview. I just need someone who uses cryptography at all on the job,
> and I just need to ask 10 questions. I would greatly appreciate it.
> You can email me at [EMAIL PROTECTED] or just reply here, although
> emails
> will catch my attention.
>
> The questions are as follows if anyone wants to just answer them:
>
> 1) How did you get into cryptography?
I've been interested in the subject since I was a kid;
when as a research student I heard about RSA, I thought
that some day, when I had spare time and CPU cycles,
I'd get around to writing a public key crypto system.
I was disappointed when I heard about PGP, that I'd been
beaten to it; but when I saw the code, I know I could
at least take satisfaction in doing it more elegantly.
Things have just continued from there
> 2) Do you feel that your work is demanding compared to other jobs?
As far as the day job goes, the crypto element is in a small
element of the product I work on; being the licensing and
data protection. As a software engineer, I don't think my job
is as demanding in many ways as teaching or nursing; but it
still takes a serious amount of dedication to keep things
going.
> 3) What kinds of people do you work with?
Software engineers
> 4) Do you enjoy what you do?
Usually - except when I find yet again that I've gotten ahead
of my schedule that my reward is to take some of the boring
tasks from other people who are behind.
> 5) Where did you get your training?
Essentially all my software and crypto experience jave come
from the University of Life.
> 6) Have you ever worked in military or defense cryptography?
No; though I have done some classified work.
> 7) Do you intend to utilize your knowledge in some way other than how you
> use it now, if so then how?
I'm utilizing it now for fun and profit; I see no reason
to do otherwise
> 8) What kind of education did you need?
I made use of the fact that I was doing post-grad research
in astrophysics to get into my first real job; and used the
experience from that to move into a more formal software
environment. Otherwise, to quote from the HitchHiker's
Guide to the Galaxy : "with one degree in maths and
another in astrophysics, it was either that or the dole
queue."
> 9) Do you require any licensing for your job?
No
> 10) What are your responsibilties on the job?
Software design implement and test; liason with customer
support; QA.
> 11) How difficult was it to find employment?
Quite easy
> 12) What is your yearly salary/hourly pay?
GBP36,300 pa
-- PGPfingerprint: BC01 5527 B493 7C9B 3C54 D1B7 248C 08BC --
_______ {pegwit v8 public key =581cbf05be9899262ab4bb6a08470}
/_ __(_)__ ___ ___ {69c10bcfbca894a5bf8d208d001b829d4d0}
/ / / / _ \/ -_|_-< www.geocities.com/SiliconValley/1394
/_/ /_/_//_/\[EMAIL PROTECTED] PGP key on page
### end pegwit v8 signed text
6a14b7d75da0c41f00ffe893dfd64e7f005b0845bfce29a697d2b273f923
c52ea07673ba61a59e2c90f738c86d3302f61f1143cf82e9204accaf7ce0
------------------------------
From: Mr. Tines <[EMAIL PROTECTED]>
Subject: Re: Trying to find simple, yet effective implementation of crypto...
Date: 19 Jan 1999 20:41 +0000
###
On Mon, 18 Jan 1999 19:37:09 -0600, in <780nlo$l93$[EMAIL PROTECTED]>
"Tim Mavers" <[EMAIL PROTECTED]> wrote.....
>
> Mr. Tines <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> >How controlled is the deployment of the client code? Does
> >your threat model encompass an attacker for whom it would be
> >worthwhile to reverse-engineer the protocol from your client
> >executable? Or to simply extract the key and just read the
> >traffic? The more determined your likely adversary, the
> >less likely simple solutions are to be robust enough.
>
> Basically I want to have two (or more) parties talk to each other. A
server
So the application is essentially a secure multi-cast chat type
of thing?
> will be provided to tell each one where they are (IP address wise).
Each
> user will have my client code. I was thinking about having each client
I get the impression that the threat model is such that you're
not intending to protect against attacks that subvert the code
at the client end. This does simplify matters.
> generate a public/private key pair, but then how do I get the keys to
each
> of the users?
Since you have a central server that is handing out the IP adresses,
it can also act as a key repository - the client should have the
server public key bundled in anyway, and it should be able to
register its key plus IP address in a single transmission when it
first joins the network (encrypted to the server, and self-signed).
The server can decrypt, check consistency and then serve it the key
and IP number together.
> Once I do get the public keys from the users, I assume I can do some sort
of
> authentication that packets received at the server (or directly to the
other
> client) are indeed coming from the right party.
Yes;
> Addtionally I have been told that I need to do a symmetric key (session
key)
> encryption for the actual messages and PKI for authentication. Bear
with
> me, I am still new to this but am very excited about learning and trying
to
> implement a somewhat secure system.
Public key systems are very slow to operate in terms of bits per second
encrypted - so its much faster to use the public key system to simply
pass a key to the conventional algorithm.
> I think the main problem right now is getting the keys exchanged.
>
> >Is this a commercial application or a hobby one? Where in
> >the world is it to be deployed? This would affect details
> >of your decision as IP issues and export controls cut in.
>
> It is just a hobby one now, but it may be commercial in the future. One
of
> the things I would like to put in is security. It doesn't have to be,
but
> it would be nice to have. The program will communicate over the
Internet.
So you would be advised to avoid IDEA or RC4 as your
conventional encryptions as they would cost money; then
you just have to worry about idiosyncratic governmental limits
on what strength of encryption system you can send to whom.
-- PGPfingerprint: BC01 5527 B493 7C9B 3C54 D1B7 248C 08BC --
_______ {pegwit v8 public key =581cbf05be9899262ab4bb6a08470}
/_ __(_)__ ___ ___ {69c10bcfbca894a5bf8d208d001b829d4d0}
/ / / / _ \/ -_|_-< www.geocities.com/SiliconValley/1394
/_/ /_/_//_/\[EMAIL PROTECTED] PGP key on page
### end pegwit v8 signed text
e5a4e619c9d803363e96362a27c5c5836477ab46bac06680df3d94b79f7e
14e036928149c73c1890284c93828aab4df4886510a4038742399d8501a1
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Date: Tue, 19 Jan 1999 22:33:53 GMT
Paul L. Allen wrote:
> It's also a truism of Turing Machines that you *cannot* tell in advance
> if a program is halting or non-halting.
That depends on what you mean by "a program". The Halting Theorem says
there's no way of writing a program that determines whether any
arbitrary turing machine you offer to it gets to a particular state
simply by inspecting the program. (Note that generally "a TM" and "a
program on a TM" are essentially the same thing; any given TM has a
program hard-wired into it. A Universal TM is one whose hard-wired
program causes it to interpret the information on its tape as a TM's
description in a very vonNeuman way.)
However, there are an infinite number of turing machines that halt, and
that you can tell halt without simulating a single instruction. There
are also an infinite number of turing machines that never halt and you
can tell never halt without simulating a single instruction. There are
also TMs you can tell will never halt simply by simulating them.
This halts: 1:HALT. This halts: 1:NOP;2:HALT. This halts:
1:NOP;2:HALT;3:NOP.
Any TM consisting only of NOPs and HALTs will halt. (Actually, these
aren't TMs, but register machines, which are computationally equivalent,
so there ya go.)
This never halts: 1:GOTO 1. This never halts: 1:NOP; 2:goto 1. Etc.
Any program consisting only of NOPs and backwards branches will never
halt, and you don't have to simulate it to determine that either.
> The only way you can tell is
> to actually run it and wait until it halts - which might be one second
> before the end of time.
Incorrect. That's only true if you're willing to take *any* TM as an
input to your algorithm. But the poster you're answering was saying that
there are programs that halt that you can tell halt, and gave examples.
Just clarifying....
--
Darren New / Senior Software Architect / MessageMedia, Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"You could even do it in C++, though that should only be done
by folks who think that self-flagellation is for the effete."
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Wed, 20 Jan 1999 02:18:50 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 19 Jan 1999 21:51:10 GMT, Darren New <[EMAIL PROTECTED]>
wrote:
>Fair enough. Chaitin defines "random" and "uncomputable" as essentially
>the same thing, which is counterintuitive to those of us who have worked
>with turing machines.
I believe Chaitin defines randomness as a property of a sequence whose
complexity cannot be reduced significantly by algorithmic means. IOW,
a number is random if there is no information at hand to make it less
complex. From that he proceeds to introduce uncomputability. His Omega
is a measure of computability (the halting probability) and because it
cannot be reduced algorithmically, it is a random number.
>No, it's not (unless the TMs it simulates are also finite). It was just
>kind of an aside, mentioned because OTP-type randomness is generally
>proven to exist by pointing at the hardware, and the ability to point at
>the hardware would eliminate the randomness of Chaitin's work.
How can that be? How can pointing at the hardware of a TM reduce the
complexity of a number like Omega? Is that your way of saying that if
you actually ran the programs subject to Chaitin's rule of no
extensions for programs that halt, then you could know all the bits of
Omega?
If so, that seems to say that you can always know if a program halts
or not by running it in a finite amount of time. But I thought that
was not possible for *all* programs, given the Turing Halting Problem.
IOW there are always some programs for which it is undecidable whether
they will ever halt or not.
>OK, I don't think I have anything more to say on this. And just to note,
>I wasn't trying to imply that what Chaitin did was either useless or
>obvious or anything. I just meant that my understanding of it seems to
>trivialize what he's saying, making it appear to be a lot of work for a
>simple idea. Obviously, it's my understanding of it that's lacking, and
>I appriciate you clarifying for me to the extent you did.
I am not sure I actually did that in a way that credits the profundity
of Chaitin's work. Therefore I recommend you read his papers for
yourself. I believe that you will find the time well spent.
Bob Knauer
"Whatever you can do, or dream you can, begin it. Boldness has
genius, power and magic in it."
--Goethe
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Wed, 20 Jan 1999 02:31:56 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 19 Jan 1999 22:08:56 GMT, Darren New <[EMAIL PROTECTED]>
wrote:
>But the fact that we can't look at it doesn't mean the answer is
>arbitrary. It just means we can't tell. This isn't quantum mechanics
>here. My point is that everything is deterministic yet infinite. It's
>the infinite part that causes the trouble, not the deterministic part.
Does what you just stated agree exactly with Turing's halting problem?
>But that has nothing to do with the halting problem. Proof: It's
>trivial to write a program that, given a number N and a program P, will
>tell you whether P will halt within N steps. It's when N is infinity
>that gives you the problem.
I thought there were instances of P with finite N where it is
impossible to find such a program to determine whether the program P
will halt or not.
What if a lone HALT instruction is placed in a location of the program
P which is never accessed? How can another program possible assess
that condition in general terms?
>I think the conclusion to the thread is that Chaitin is defining
>"random" in an unusual way, which leads people to talk about
>deterministic machines as behaving randomly, when what they really mean
>is that some aspect of the machine's behavior is not predictable by
>another program (namely, that the machine will never reach a certain
>state-space or will reach a certain state-space).
I thought that was the essence of Turing's halting problem.
Another deterministic system, a formal axiomatic system, contains
propositions that are indeterminant - as in Godel's Theorem.
>The set of states the machine goes through are well-defined, but may be
>infinite in size. Whether the set of states the machine goes thru is
>infinite in size is what determines whether it halts, but given a state
>for the machine, there is zero randomness about where it will go next,
>and for any given machine its set of reachable states is either finite
>or infinite. You just can't tell without generating them all. The
>machine isn't behaving randomly, tho, and I hence claim that for any
>given machine, whether it halts or not is 100% deterministic.
How? If the machine never halts in a finite amount of time, yet there
is a HALT instruction present (which means it could halt in
principle), how can you determine algorithmically that it will or will
not halt in general terms?
>But again, to conclude, Chaitin defines "random" in his own way
>(something about ten bits of compression, apparently), and hence the
>whole discussion of what it means to be random becomes rather mood.
>Thanks!
It ain't over yet - the fat lady still has to sing.
Bob Knauer
"Whatever you can do, or dream you can, begin it. Boldness has
genius, power and magic in it."
--Goethe
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: Re: Metaphysics Of Randomness
Date: Wed, 20 Jan 1999 02:37:23 GMT
> >No, it's not (unless the TMs it simulates are also finite). It was just
> >kind of an aside, mentioned because OTP-type randomness is generally
> >proven to exist by pointing at the hardware, and the ability to point at
> >the hardware would eliminate the randomness of Chaitin's work.
>
> How can that be? How can pointing at the hardware of a TM reduce the
> complexity of a number like Omega? Is that your way of saying that if
> you actually ran the programs subject to Chaitin's rule of no
> extensions for programs that halt, then you could know all the bits of
> Omega?
No. I'm saying that it is impossible to actually build a piece of
hardware that will run a program for which you cannot tell whether it
will halt. If your program only has a finite space to work in, then you
can write another program that will tell you whether it will halt.
> If so, that seems to say that you can always know if a program halts
> or not by running it in a finite amount of time.
No. If your program is limited to what will run on real hardware you can
really point to, then the halting problem goes away.
> But I thought that
> was not possible for *all* programs, given the Turing Halting Problem.
It's not possible for all programs on turing machines, because turing
machines are infinite in size.
Here's a proof:
You build a machine that has finite storage, and you put a finite
program on it. Count the "program counter" as part of the finite
storage. There will be no more than (say) 2^N possible states the finite
storage can be in, for some N. (If the storage is binary, then N is the
number of bits of storage you have.) Build a machine that has something
more than 2^(2^N) bits of storage, clear 2^N "flag" bits, and start
simulating the first program. Every time it gets to a particular state,
try to set the associated flag bit for that state. If the program you
are simulating gets to a halt state before you try to set a flag bit
twice, then it halts. If you try to set a flag bit that's already set
before the simulated program halts, then the program will never halt,
since the machine you're simulating is deterministic. Since you only set
bits and never clear them, this algorithm is known to terminate.
This doesn't work if you don't have an upper limit on the number of flag
bits you need before you start simulating the machine.
> IOW there are always some programs for which it is undecidable whether
> they will ever halt or not.
Right. I'm assuming you know how the proof goes. Actually, the precise
definition is that there is no one program which, when given encodings
of all turing-complete programs, can determine whether every one reaches
a particular state (the halt state) or not. Obviously, it's possible to
design programming languages that you can prove always lead to halting
programs, but these have functions (like Ackerman's function) which
cannot be computed by programs in those languages.
> >I appriciate you clarifying for me to the extent you did.
>
> I am not sure I actually did that in a way that credits the profundity
> of Chaitin's work. Therefore I recommend you read his papers for
> yourself. I believe that you will find the time well spent.
Right. I shall. I still think the main problem is he defines words in
an unusual way, which is fine unless you're trying to understand it
without the definitions. :-)
--
Darren New / Senior Software Architect / MessageMedia, Inc.
San Diego, CA, USA (PST). Cryptokeys on demand.
"You could even do it in C++, though that should only be done
by folks who think that self-flagellation is for the effete."
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Metaphysics Of Randomness
Date: Wed, 20 Jan 1999 02:58:08 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 20 Jan 1999 01:20:58 GMT, Darren New <[EMAIL PROTECTED]>
wrote:
>And if Omega is one bit for each valid program (which is
>not what I read in the lecture *I* read), then Omega seems poorly
>defined.
That is not how Omega is defined.
>I would think if a program is well-defined, it will either try to
>execute "off the end" so to speak, or it will run entirely within the
>bits. Assuming the number is an encoding of the state machine and the
>initial tape, for example. He must be doing something unusual with his
>TMs too.
>Hmmm, actually, I'll have to read how he defines his UTM, since it would
>seem that an encoding of an infinite machine in a finite number of bits
>would leave an infinite number of default values on the tape, and a
>longer number might very well change whether the exact same program
>halts, by changing defaults that the halting program reads and acts on.
>Evidently, he's not using the usual definitions of UTM.
Chaitin likes to modify things. He even modified LISP to accomodate
his needs.
>And I'm unclear on how one throws out extentions to halting programs
>without knowing which are the halting programs.
He talks about "self-limiting" programs.
>> But Omega IS incalculable - that's why he considers it random.
>You're using a definition for Omega different than the one I read of in
>the lecture I read, so I'll have to find the one you're referring to.
In another paper he discusses how Omega is uncalculable - that each of
the bits of Omega are completely indeterminant, just like his
exponential diophantine equation is indeterminant for any parameter
value.
He states that each of the bits of Omega are related directly to
whether a given exponential diophantine equation has a finite number
of solutions (in which case the corresponding bit of Omega is 0) or
whether it has an infinite number of solutions (in which case the
corresponding bit of Omega is 1).
>No. Even if you don't run it. Either it'll halt were you to run it long
>enough, or it wouldn't halt were you to run it no matter how long you
>let it run. There's no need to run it to classify it as a program that
>halts or not in order to know that. That's the point I've been trying to
>make. You only need to run it to find out whether it halts or not,
>assuming it halts and you run it long enough.
That does not seem to agree with what is contained in Turing's halting
problem.
>Point taken. Omega itself may seem pretty trivial,
Omega is intimately related to the Turing halting problem, which seems
to say that it is hardly trivial.
> but its consequences
>might be more important to one more knowlegable in math than I am. I'm
>not sure why it's less trivial than the halting problem itself, but I
>haven't followed it enough to know.
It is not more or less trivial than the halting problem - it is an
expression of the halting problem.
>Omega itself sounds like it would be an unknowable number as well.
That is what is meant by the indeterminism of Omega. Every bit is
indeterminant.
>Maybe that's part of what's meant. I mean, I can make up lots of numbers that
>are indeterminant and unpredictable algorithmically. It's what you can
>do with Omega after that that makes it interesting, I guess.
Or its relationship with other concepts.
>It *is* deterministic. It's merely uncalculable. But it's value doesn't
>change from moment to moment.
It does not have a value. Each bit is indeterminate.
>Just like whether that nucleus popped five minutes ago is deterministic:
>yes or no, 100% or 0%. It's only unclear if you start talking about the
>future.
I think you are using the term "deterministic" in a much different
sense than what Chaitin means by it. He means (and I have followed his
convention) that something is algoritmically indeterminant. In that
sense, you cannot calculate the individual bits of Omega, or calculate
the time of the individual decays of a radioisotope.
You are using the term in the sense of state machine determinism, that
each state follows from a prior deterministic state. But that is also
true of formal axiomatic systems, and yet there are propositions in
those systems which cannot be decided formally - that is, they are
indeterminate in the sense Chaitin means by the term.
>But that won't tell you whether it halts. That's the point of the
>halting problem. Running the program doesn't reliably tell you whether
>it halts.
We seem to be going in circles here. You make a point about
determinism and I concede your point for the sake of discussion. Then
later you make the opposite point to show my concession is wrong -
never mind that my concession was based on your original contention.
Please explain your take on the halting problem in unequivocal terms
so we can have a point of departure for subsequent discussions. Can it
be determined algorithmically whether any general program halts or
not? Can it be determined experimentally whether any general program
halts or not?
Will the real Halting Problem please stand up! :-)
>Right. And that only happens because TMs are infinite. It isn't because
>TMs are nondeterministic. It's because they're infinite in size.
Again you seem to be using the term "deterministic" in a different way
from what Chaitin means and what I always thought was meant. To me,
determinism means exactly what it says - that something can be
determined unambiguously.
Just because each state of a TM is deterministic does not mean that
the halting or non-halting of any program is deterministic, any more
than the fact that a formal axiomatic system is deterministic yet
there are propositions which are indeterminate.
Bob Knauer
"Whatever you can do, or dream you can, begin it. Boldness has
genius, power and magic in it."
--Goethe
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
