HDTenEightyP/NetNews huggingface dataset:
From: tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman)
Subject: Gates vs Turing machines
Date: 16 Oct 92 02:59:19 MDT
Organization: University of Utah, CompSci Dept

  How could a linear collection of gates simulate a Turing machine?
Or, how could a boolean expression simulate a Turing machine?

The Turing machine is an interesting object (and gets the halting uncertainty)
only because it does not always move in one direction, it cycles and
repeats sometimes.  However a linear collection of gates clearly could
not do anything but come to its end, how can it simulate a Turing machine?
What else is needed to make the gates function as a real computer, besides
them hooked together?

Newsgroups: comp.theory
From: wanka@uni-paderborn.de (Rolf Wanka)
Subject: Re: Combinatorial Problem
Reply-To: wanka@uni-paderborn.de
Organization: Uni-GH Paderborn, Germany
Date: Thu, 8 Oct 1992 07:27:37 GMT

In article <dak.718420477@messua>, dak@messua.informatik.rwth-aachen.de (David Kastrup) writes:
|> wanka@uni-paderborn.de (Rolf Wanka) writes:
|> 
|> >Dear Theory Community:
|> 
|> >I think the following problem has been investigated (and solved)
|> >before it came to my desk.
|> 
|> >Given: An m-sided d-dimensional array consisting of N=m^d nodes,
|> >       numbered from (0,..,0) through (m-1,..,m-1).
|> 
|> >Task:  Compute the number X of nodes that have exact distance i from
|> >       the node numbered (0,..,0).
|> 
|> >This number X is very easy determined on the hypercube, for instance, and
|> >it is a nice exercise to compute X, if i<m.
|> 
|> >But it seems difficult to give a general formula (consisting of
|> >binomials, ...) for X.
|> 
|> First thing necessary to know would be your definition of distance.
|> Taxi? Euclidean? Reachable by i moves?

Sorry, if my question was posed too inexactly. The term `distance' means
the length of a shortest path between two nodes of the array
(
 notes:
     (i)  this is what is refered to Manhattan or Taxi distance;
     (ii) it is a discrete problem
).

E.g. on the 4-sided 2-dimensional array:

      00  01  02  03

      10  11  12  13

      20  21  22  23

      30  31  32  33


The nodes {20, 11, 02} have distance 2 from node 00.

Also, my question can be reformulated as follows:

Given: delta, m, d

Compute the number X of tuples (a_1,...,a_d) such that

             d
           -----
           \    
(1)         )     a  =  delta
           /       i
           -----
           i = 1


(2)       for all a :  0  =<  a   <  m
                   i           i

Condition (2) is what makes things difficult on higher dimensions.
Without (2) (or equivalently in general, if delta < m), we have 

                    /  d+delta-1  \
           X   =    |             |
                    \    d - 1    /

Meanwhile, I got a reference for this problem, where some
approximations were computed:

    A. L. Rosenberg, Preserving proximity in arrays,
    SIAM J. Comp. 4 (1975) 443-460

Thanks to all who tried two help me.

	Rolf Wanka
--------------------------------------------------------------------------
 Rolf Wanka                           | e-mail: wanka@uni-paderborn.de 
 Universitaet-GH Paderborn            | or:     wanka@pbinfo.uucp
 Fachbereich 17-Mathematik/Informatik | or:   ...!uunet!unido!pbinfo!wanka
 Warburger Str. 100                   | FAX:   +49 5251 603836
 D-W-4790 Paderborn, Germany          | Phone: +49 5251 603309
--------------------------------------------------------------------------
 
Newsgroups: comp.theory
From: tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman)
Subject: Good grad schools for theory
Date: 9 Oct 92 13:36:15 MDT
Organization: University of Utah, CompSci Dept

What are the best graduate programs in computer theory?  Specifically, in
nondeterministic computation, information theory, and cellular automata?

Any programs with active research in the above would be great.

Thanks for any information!


Newsgroups: comp.theory
From: spworley@netcom.com (Steven)
Subject: Multidimensional Hashing
Organization: Netcom - Online Communication Services  (408 241-9760 guest) 
Date: Thu, 15 Oct 1992 05:31:29 GMT

I'm writing an application that computes random numbers at integer
gridpoints on a 3D lattice. Since I want speedy computation and don't
care about a large range, I want to use the grid's X,Y,Z location to
set up a lookup into a table of pre-computed numbers. [This also lets
me set up any distribution of random numbers I like!]

This is a hashing problem: I want to take a value, and pseudo-randomly
look up values in a table. If the grid were a one-D line, this is a
standard hashing problem, and there are dozens of algorithms that will
work, Fibonnaci hashing probably being the best. But my lattice
is THREE dimensional, and I want to use all three lattice locations.
Unfortunaly Knuth (God of Algorithms) never speaks of this sort of
hashing in Art of Programming, and Cormen's "Intro to Algorithms" doesn't
ether.

One solution is to just hash each variable X,Y,Z, and have a three D
table of random numbers. But this is bad: if you have an 8x8x8 hash
table, as you traverse in one direction along the axes, only one
coordinate would change: Two of the hashed varaibles would be
constant, and only one would vary. This means you get the same 8
numbers back each time, though somewhat randomly if the 1D hash is
good. This is BAD.

So, ok, why not use a 1D hash, and just somehow combine the three 
coordinates into one number, and use that as the hash index? Ie,
hash (X+Y+Z) into a 1D table?  This also doesn't work. There's a rich
exploration of the full table, but spacially, the (0 0 1) value is the
same as (0 -1 2) and (0 1 0) and ( 1 -1 1) and an infinite number
of other pairs. A function like X+5*Y+13*Z is much better, but will
still have lines where the same hash value will occur.

My best though is to use the second idea, but make that function very
nonlinear. Perhaps (XY(Z+1)+X(Y+1)Z+(X+1)YZ). But this takes LOTS of
computation (hashes need to be *FAST*) and I know enough about hashes
and pseudorandom algorithms to know that if you arbitrarily pick
something that "seems good" you often get horrible performance.

--

So what is the proper way to make a 3D hash? I don't want any simple
correlation between ajacient gridpoints, and no repeating of "blocks"
over and over. I want to use a full set of random numbers (256 is
probably right). I don't see an easy way to do this except to use some
very nonlinear formula to map X,Y,Z to W, and use W to hash with. In
this case, what formula is fast, but "nonlinear" enough?

Thanks for any help you guys can give me!

-Steve
spworley@netcom.com
Newsgroups: comp.theory
From: egon@uni-paderborn.de (Egon Wanke)
Subject: bounded integer sum
Keywords: 
 
 
Organization: Uni-GH Paderborn, Germany
Date: Wed, 14 Oct 1992 13:28:19 GMT

Is there anybody who knows something about the complexity of
the following simple number problem:

Given: Nonnegative integers   s,t,m,
               and integers   x_1,...,x_n,

Question: Is there a nonempty sequence of integers y_1,...,y_k
          each y_j from {x_1,...,x_n}, such that

                   k
            s  +  sum  y_j     =   t
                  j=1
and

                   l
     0  <=  s  +  sum  y_j     <=  m     for l=1,...,k ?
                  j=1


Note that k may be greater than n.

The problem is obviously NP-hard and in PSPACE.
But is it known to be in NP or hard for PSPACE?

Any reference would greatly appreciated.

Egon Wanke
University of Paderborn
Dept.. of Mathematics and Computer Science
W-4790 Paderborn

egon@uni-paderborn.de


Xref: sparky comp.theory:2172 rec.puzzles:6740
From: wsadjw@rw7.urc.tue.nl (Jan Willem Nienhuys)
Newsgroups: comp.theory,rec.puzzles
Subject: Re: Penrose Tiles / Beatty Seq's.
Date: 12 Oct 92 13:45:03 GMT
Reply-To: wsadjw@urc.tue.nl
Followup-To: comp.theory
Organization: Eindhoven University of Technology, The Netherlands

In article <18007@ucdavis.ucdavis.edu> shaw@toadflax.UCDavis.EDU (Rob Shaw) writes:
#
#A while ago I was reading a Gardner-ish rec math book, and
#it contained an update about Penrose tilings. I would 
#..
#strips. The sequence is a Beatty sequence.
#
#Something like 
#
#10010101001010010010010...
#
#Could be a Beatty sequence, since one of the two elements
#always appears alone, and the other appears alone or in
#pairs.
#
#This is all from memory, so I may have gotten a few things
#confused...
#
#Please, anyone who can give me pointers to books/articles
#about this material, please post or email.

The poster Bob Shaw might be interested in:
N.G. de Bruijn
Updown generation of Beatty sequences,
Proceedings of the Kon. Ned. Ak. Wet., series A, vol. 92 (1989),
(= Indagationes Mathematicae 51)
p. 385-407.

That's the same De Bruijn of "DeBruijn-cycles", who happens to
occupy the office opposite me; he can be reached at wsdwnb@win.tue.nl,
he will gladly send you an offprint, I guess.

JWN
From: jsv@CS.BROWN.EDU (Jeff Vitter)
Newsgroups: comp.theory
Subject: bibliographies
Date: 14 Oct 92 17:05:09 GMT
Reply-To: Jeff Vitter <jsv@cs.brown.edu>

I'm interested in compiling a list of available large-scale on-line
bibliographies, both on general and specialized topics of algorithms
and theoretical CS.  If you have one or more such bibliographies (or
know of some) whose availability would benefit the general community,
please let me know.  It's not important that they be remotely
accessible at the moment.

Thanks.
   -- Jeff

Prof. Jeff Vitter                     email: jsv@cs.brown.edu
Dept. of Computer Science             phone: (401) 863-7646
Brown University                      FAX:   (401) 863-7657
Providence, R.I. 02912-1910           home:  (401) 831-6836
Xref: sparky comp.theory:2159 sci.math:12948
From: mike@park.bu.edu (Michael Cohen)
Newsgroups: comp.theory.dynamic-sys
Subject: Re: Attractors
Date: 17 Oct 92 04:15:14 GMT
Organization: Boston University

I wrote down a construction with just polynomials that is easily
capable of attracting to two and three Torus's.  I haven't figured
out how to attract to Mobius strips as yet.  A much more general
construction which does this and more is
written in my January 1992 paper in Neural Networks.

Briefly Let H = x^2 + y^2 
            G = z^2 + w^2

Let A(H) =( H -1)^2
    B(G) =( G -3)^2


Let b and c be positiveconstants whose ratio are irrational.  Let 

V(x,y,z,w) = [A'(H)H_x, A'(H)H_y, B'(G)G_z, B'(G)H_w] let
X = [x,y,z,w]  then a system which does the job (generates two torus's
as attractors using polynomials only is the following).  Three Torus's
are quite similar.

dX^t/dt =- QV^t + [bH_y, -bH_x, cG_w, -cG_z]^t where ^t denotes
transpose and Q is a Riemannian metric, a polynmomial matrix which is
globally positive definite.
                -mike









-- 
Boston University (617-353-7857) Email: mike@park.bu.edu
Smail: Michael Cohen                     111 Cummington Street, RM 242
       Center for Adaptive Systems        Boston, Mass 02215
       Boston University
From: sandyp@ims.com (Sandy Profeta)
Subject: Dynamic modeling of physical systems
Originator: sandyp@motmot
Organization: Integrated Measurement Systems, Inc.
Distribution: usa
Date: Fri, 9 Oct 1992 18:42:56 GMT

I have a friend who is interested in finding the appropriate news group
to discuss issues around dynamic modeling of physical systems.  He's
just purchased some software called ADAMS and is looking for others
who might be using this software or are doing this kind of modeling.

Is this the right group, or can anyone suggest a better one?



-- 
sandyp@ims.com
Integrated Measurement Systems
9525 SW Gemini Drive.  Beaverton, OR  97005  Phone: (503) 626-7117
****	"I'd rather be playing Irish music on my mandolin." ***
From: lakerb@rcwusr.bp.com
Newsgroups: comp.theory.dynamic-sys
Subject: Re: spinning beam vibration
Date: 12 Oct 92 11:20:36 -0500
Organization: BP Research, Cleveland, OH (USA)

In article <1992Oct11.220243.17946@serval.net.wsu.edu>, pmiles@em9.eecs.wsu.edu (Kilroy was here) writes:
> 
> Could someone send me a list of sources on modeling a cantilever beam 
> where the beam length is along the z-axis, there is a set of nonlinear
> forces applied to the beam in both the x and y directions and the beam
> is spinning clockwise about the z-axis.
> 
> I am having trouble finding a good numerical model for this system. Any
> info will be greatly appreciated.   Thanks  :)
> 

It's not quite clear whether you need a static or dynamic model.  If dynamic,
the approach is likely to be an eigenfunction model, with each mode excited by
the non-linear forces.  Another approach is the finite-element model, with a
mesh of interconnected nodes and forces at the appropriate node points.

I'm not current on the texts or literature.

Rob Lake
BP Research
lake@rcwcl1.dnet.bp.com

Newsgroups: comp.theory.dynamic-sys
From: pmiles@em9.eecs.wsu.edu (Kilroy was here)
Subject: spinning beam vibration
Keywords: beam vibration
Organization: Washington State University
Date: Sun, 11 Oct 92 22:02:43 GMT


Could someone send me a list of sources on modeling a cantilever beam 
where the beam length is along the z-axis, there is a set of nonlinear
forces applied to the beam in both the x and y directions and the beam
is spinning clockwise about the z-axis.

I am having trouble finding a good numerical model for this system. Any
info will be greatly appreciated.   Thanks  :)

--
Peter J. Miles             Once a Marine Always a Marine 
pmiles@eecs.wsu.edu               Semper Fi  !!!!
From: sprott@128.104.39.173 (Sprott@Juno.Physics.Wisc.Edu)
Newsgroups: comp.theory.dynamic-sys
Subject: Attractors
Date: 16 Oct 92 14:47:10 GMT
Reply-To: sprott@128.104.39.173 (Sprott@Juno.Physics.Wisc.Edu)
Organization: Univ. of Wisconsin, Plasma Physics

Does anyone know of a mapping or system of ordinary differential equations
involving only polynomials whose solution attracts to:
     a) a 2-torus
     b) a 3-torus
     c) a Moebius strip?
From: bradford@beldar.cs.indiana.edu (Phil Bradford)
Newsgroups: comp.theory
Subject: word problems on lattices
Keywords: lattice, word problems, complexity, decidability
Date: 16 Oct 92 21:10:33 GMT
Article-I.D.: news.1992Oct16.161039.16973
Organization: Computer Science, Indiana University


	Hi,

Could anyone supply me with references to the complexity of 
solving word problems on (non-distributive) lattices?

thanks,
phil
Phillip Gnassi Bradford: bradford@cs.indiana.edu, 
215 Lindley Hall, Computer Science Dept., Indiana Univ., 
Bloomington, IN 47405.
-- 
Phillip Gnassi Bradford: bradford@beldar.cs.indiana.edu, 
215 Lindley Hall, Computer Science Dept., Indiana Univ., Bloomginton, 
IN 47405.
Xref: sparky comp.theory:2174 sci.math:13101
From: pdc@dcs.ed.ac.uk (Paul Crowley)
Newsgroups: comp.theory,sci.math
Subject: Re: Turing's Halting problem revisited
Date: 13 Oct 92 14:19:09 GMT
Reply-To: pdc@dcs.ed.ac.uk (Paul Crowley)
Organization: Laboratory for the Foundations of Computer Science, Edinburgh U

In article <Oct09.020143.90256@yuma.ACNS.ColoState.EDU> ld231782@LANCE.ColoState.Edu (L. Detweiler) writes:
>H(x,y) surely does not exist, and perhaps neither does H'(x,y).  However,
>the `halting problem' is so important that an algorithm even for restricted
>inputs could potentially resolve many currently unsolved problems.  Hence, 
>let
>
>H2(x,y) = 2 if [...]
>H2(x,y) = 0 if x(y) hangs
>H2(x,y) = 1 if x(y) halts
>
>What is the least restrictive filter [...] such that H2(x,y) exists?

No such least restrictive filter exists.  For any such filter, programs exist
such that it answers '2'.  Such a filter can be enhanced with a check for
one or more of these specific tuples of programs and inputs and gives the
appropriate answer, making it a slightly better answer.  Perhaps, however,
there are good tests that solve the halting problem for some large class
of programs for which the answer is not obvious.  "lint" occasionally warns
that a program doesn't halt, and a program with no loops or recursion must
halt, but these cases are trivial.  I suspect that an answer would resemble
Maple or Mathematica in some respects, and a program optimiser in others.
--
  __                                ____
\/ o\ Paul Crowley pdc@dcs.ed.ac.uk \  /
/\__/ "SET ME ON FIRE!" - Big Black  \/
Newsgroups: comp.speech
From: pyeatt@Texaco.com (Larry D. Pyeatt)
Subject: Re: can you recommend a grad school ?
Organization: Texaco
Date: Fri, 9 Oct 1992 21:25:50 GMT

In article <1992Oct9.130225.14639@hubcap.clemson.edu>, bdbryan@eng.clemson.edu (Ben Bryant) writes:
|> In article aa27929@Bonnie.ics.uci.edu, amilota@Bonnie.ICS.UCI.EDU () writes:
|> >Hello out there!
|> >Can anyone recommend or at least name some Universities where they are working
|> >on voice recognition and give PHDs for studying it.
|> >I know that Carnegie Melon and MIT are particualrly big in the field,
|> >but can anyone think of any others.
|> >I am more interested in developing applications and in teraction paradigm
|> >then working on DSP and pattern recognition.
|> >Thanks.
|> >A'
|> >"Beware the Mutant"
|> 
|> I agree. I too am looking for a good PhD school to further studies in
|> the speech area. -Thanks in advance.
|> 

You might try Texas Tech Computer Science department.  I did my M.S. in 
speech recognition there.  You should contact Dr. Thomas English or
Dr. William J. B. Oldham.  Tom is especially knowledgeable about SR, but
I think he already has 5 grad students.  Oldham, has 7 students and
works in Neural Networks.  They have had a flood of grad students and
will not admit anyone until next fall, so get your application in
early. :^)

-- 
Larry D. Pyeatt                 The views expressed here are not
Internet : pyeatt@texaco.com    those of my employer or of anyone
Voice    : (713) 975-4056       that I know of with the possible
                                exception of myself.
Newsgroups: comp.speech
From: lseltzer@phoenix.Princeton.EDU (Linda Ann Seltzer)
Subject: Re: Phoneme prog/data for SGI Indigo?
Originator: news@nimaster
Organization: Princeton University
Date: Wed, 7 Oct 1992 14:57:16 GMT

>Does anybody have a Phoneme-based or just plain
>ANY speech generation program for the Indigo?

There are two parts to a speech synthesis system: (1) the program
that synthesizes the samples and (2) the rules which provide the
proper information to the synthesizer program.  Dennis Klatt's
1980 JASA paper contains Fortran code that you can translate to
C for generating the sound samples.  There are errors in the
paper and in the Fortran program, though.  As for the rule program,
I don't know of any publicly available software.  It takes so many
years for a group of linguists to develop it, that it's not the
sort of thing one obtains for free.  You can buy speech synthesis from
Centigram in San Jose.  As long as the synthesis program writes samples
into a file in a format the Ingido knows about, then any rule program
in a language compilable on the Indigo should work - your synthesis
program just has to read the output.

Newsgroups: comp.speech
From: dfrankow@myria.cs.umn.edu (Dan Frankowski)
Subject: Re: Looking for VOC and WAB formats
Organization: University of Minnesota
Date: Thu, 8 Oct 1992 16:36:38 GMT

In <1992Oct6.151318.24957@news.iastate.edu> horacio@iastate.edu (Horacio Martinez-Alfaro) writes:

>Does anyone have some information on how files are written (structure)
>with these formats ? I need to have access to voice data written with
>those formats. Thanks in advanced for your help.

>-- Horacio.

Go to comp.dsp (or news.answers, or other crosspostings) and look for
the "Audio File Formats" FAQ by Guido van Rossum.  It has VOC and WAV
formats.

Dan

--
Dan Frankowski                dfrankow@cs.umn.edu
From: Paul Placeway <pplacewa@bbn.com>
Newsgroups: comp.speech
Subject: Re: Help on design of speech recognition
Date: 15 Oct 1992 15:32:29 GMT
NNTP-Posting-Host: bbn.com
Keywords: speech recognition

tridge@nimbus.anu.edu.au (Andrew Tridgell) writes:

< In article <lels.9.718355427@unpcs1.cs.unp.ac.za>, lels@unpcs1.cs.unp.ac.za (Leonard Els) writes:
< |> I am working on a Speaker Independant Speech Recognition system and was
< |> wondering what the best measurements are, to use in the analysis.
< |> 
< |> I have come accross the following: Zero-Crossing rate, Energy, LPC,
< |> Cepstral Coefficients, and formant analysis

< For speaker independant recognition the most popular are probably 
< the cepstrals. 

< There are problems with using formants - not the least of which is 
< find how to calculate them! If you know of some way to robustly 
< calculate their values in a speaker independant way then please share 
< it with us.

< My own personal favourite is the engineering approach. This is to throw
< all the ingredients which might be useful into a cooking pot and stir
< vigorously.

< The way I do this is to use LDA (linear discriminant analysis) on a
< feature vector comprising a few of the common parameters (maybe cepstrals, delta-cepstrals, band-power, delta-band-power, zcr and energy). This
< gives me a new feature vector of reduced dimension, but where each
< parameter has a high discrimination for the task at hand.


What parameters to use partially depends on the signal-to-noise of the
speech.  For high SNR (eg. quiet office environment), the current best
that I know if is using a combination of Cepstra, first- and
second-difference-Cepstra, energy (generally across the whole band,
normalized in some way), and first- and second-difference-non-normalized
energy.  There are several ways of getting the cepstral coefficients
that all seem to be pretty good, the most common being LPC-Cepstra and
FFT-Cepstra (see Oppenheim and Schafer).  Some groups also use LSP
analysis with good results.

Also, for medium SNR, much work has been done to normalize the Cepstra
in various ways to compensate for channel and noise differences
between training and test conditions.

Good ZCR analysis may be better in very low SNR conditions (like 0 to
10 db SNR), but seems to be inferior in high SNR.

I'm dubious of formant analysis, mostly because it depends on using
Cepstra or LPC or LSP analysis, and my experience is that making a
hard decision before letting a stochastic pattern match figure things
out is almost always a mistake.  Just send the Cepstra/LPC/LSP/Wavelet/
whatever into the HMM/ANN/SSM/whatever model and let it figure it out.

LDA is quite effective at removing redundancy from a high
dimensionality signal.  Another technique that we have found to be
quite effective is the use of maximum mutual information to determine
how to weight a set of features for best performance.

		-- Paul Placeway <pplacewa@bbn.com>
		   BBN Speech and Natural Language.
Newsgroups: comp.speech