Kolmogorov A.N., Local Structure of Turbulence in Viscous Fluid(1941)

Aabsolute value 绝对值accept 接受acceptable region 接受域additivity 可加性adjusted 调整的alternative hypothesis 对立假设analysis 分析analysis of covariance 协方差分析analysis of variance 方差分析arithmetic mean 算术平均值association 相关性assumption 假设assumption checking 假设检验availability 有效度average 均值Bbalanced 平衡的band 带宽bar chart 条形图beta-distribution 贝塔分布between groups 组间的bias 偏倚binomial distribution 二项分布binomial test 二项检验Ccalculate 计算case 个案category 类别center of gravity 重心central tendency 中心趋势chi-square distribution 卡方分布chi-square test 卡方检验classify 分类cluster analysis 聚类分析coefficient 系数coefficient of correlation 相关系数collinearity 共线性column 列compare 比较comparison 对照components 构成，分量compound 复合的confidence interval 置信区间consistency 一致性constant 常数continuous variable 连续变量control charts 控制图correlation 相关covariance 协方差covariance matrix 协方差矩阵critical point 临界点critical value 临界值crosstab 列联表cubic 三次的，立方的cubic term 三次项cumulative distributionfunction 累加分布函数curve estimation 曲线估计Ddata 数据default 默认的definition 定义deleted residual 剔除残差density function 密度函数dependent variable 因变量description 描述design of experiment 试验设计deviations 差异df.(degree of freedom) 自由度diagnostic 诊断dimension 维discrete variable 离散变量discriminant function 判别函数discriminatory analysis 判别分析distance 距离distribution 分布D-optimal design D-优化设计Eeaqual 相等effects of interaction 交互效应efficiency 有效性eigenvalue 特征值equal size 等含量equation 方程error 误差estimate 估计estimation of parameters参数估计estimations 估计量evaluate 衡量exact value 精确值expectation 期望expected value 期望值exponential 指数的exponential distributon 指数分布extreme value 极值Ffactor 因素，因子factor analysis 因子分析factor score 因子得分factorial designs 析因设计factorial experiment 析因试验fit 拟合fitted line 拟合线fitted value 拟合值fixed model 固定模型fixed variable 固定变量fractional factorial design部分析因设计frequency 频数F-test F检验full factorial design 完全析因设计function 函数Ggamma distribution 伽玛分布geometric mean 几何均值group 组Hharmomic mean 调和均值heterogeneity 不齐性histogram 直方图homogeneity 齐性homogeneity of variance 方差齐性hypothesis 假设hypothesis test 假设检验Iindependence 独立independent variable 自变量independent-samples 独立样本index 指数index of correlation 相关指数interaction 交互作用interclass correlation 组内相关interval estimate 区间估计intraclass correlation 组间相关inverse 倒数的iterate 迭代Kkernal 核Kolmogorov-Smirnov test 柯尔莫哥洛夫-斯米诺夫检验kurtosis 峰度Llarge sample problem 大样本问题layer 层least-significant difference 最小显著差数least-square estimation 最小二乘估计least-square method 最小二乘法level 水平level of significance 显著性水平leverage value 中心化杠杆值life 寿命life test 寿命试验likelihood function 似然函数likelihood ratio test 似然比检验linear 线性的linear estimator 线性估计linear model 线性模型linear regression 线性回归linear relation 线性关系linear term 线性项logarithmic 对数的logarithms 对数logistic 逻辑的lost function 损失函数Mmain effect 主效应matrix 矩阵maximum 最大值maximum likelihoodestimation 极大似然估计mean squareddeviation(MSD) 均方差mean sum of square 均方和measure 衡量media 中位数M-estimator M估计minimum 最小值missing values 缺失值mixed model 混合模型mode 众数model 模型Monte Carle method 蒙特卡罗法moving average 移动平均值multicollinearity 多元共线性multiple comparison 多重比较multiple correlation 多重相关multiple correlationcoefficient 复相关系数multiple correlationcoefficient 多元相关系数multiple regression analysis多元回归分析multiple regressionequation 多元回归方程multiple response 多响应multivariate analysis 多元分析Nnegative relationship 负相关nonadditively 不可加性nonlinear 非线性nonlinear regression 非线性回归noparametric tests 非参数检验normal distribution 正态分布null hypothesis 零假设number of cases 个案数Oone-sample 单样本one-tailed test 单侧检验one-way ANOVA 单向方差分析one-way classification 单向分类optimal 优化的optimum allocation 最优配制order 排序order statistics 次序统计量origin 原点orthogonal 正交的outliers 异常值Ppaired observations 成对观测数据paired-sample 成对样本parameter 参数parameter estimation 参数估计partial correlation 偏相关partial correlation coefficient 偏相关系数partial regression coefficient 偏回归系数percent 百分数percentiles 百分位数pie chart 饼图point estimate 点估计poisson distribution 泊松分布polynomial curve 多项式曲线polynomial regression 多项式回归polynomials 多项式positive relationship 正相关power 幂P-P plot P-P概率图predict 预测predicted value 预测值prediction intervals 预测区间principal component analysis 主成分分析proability 概率probability density function 概率密度函数probit analysis 概率分析proportion 比例Qqadratic 二次的Q-Q plot Q-Q概率图quadratic term 二次项quality control 质量控制quantitative 数量的，度量的quartiles 四分位数Rrandom 随机的random number 随机数random number 随机数random sampling 随机取样random seed 随机数种子random variable 随机变量randomization 随机化range 极差rank 秩rank correlation 秩相关rank statistic 秩统计量regression analysis 回归分析regression coefficient 回归系数regression line 回归线reject 拒绝rejection region 拒绝域relationship 关系reliability 可靠性repeated 重复的report 报告，报表residual 残差residual sum of squares 剩余平方和response 响应risk function 风险函数robustness 稳健性root mean square 标准差row 行run 游程run test 游程检验Ssample 样本sample size 样本容量sample space 样本空间sampling 取样sampling inspection 抽样检验scatter chart 散点图S-curve S形曲线separately 单独地sets 集合sign test 符号检验significance 显著性significance level 显著性水平significance testing 显著性检验significant 显著的，有效的significant digits 有效数字skewed distribution 偏态分布skewness 偏度small sample problem 小样本问题smooth 平滑sort 排序soruces of variation 方差来源space 空间spread 扩展square 平方standard deviation 标准离差standard error of mean 均值的标准误差standardization 标准化standardize 标准化statistic 统计量statistical quality control 统计质量控制std. residual 标准残差stepwise regressionanalysis 逐步回归stimulus 刺激strong assumption 强假设stud. deleted residual 学生化剔除残差stud. residual 学生化残差subsamples 次级样本sufficient statistic 充分统计量sum 和sum of squares 平方和summary 概括，综述Ttable 表t-distribution t分布test 检验test criterion 检验判据test for linearity 线性检验test of goodness of fit 拟合优度检验test of homogeneity 齐性检验test of independence 独立性检验test rules 检验法则test statistics 检验统计量testing function 检验函数time series 时间序列tolerance limits 容许限total 总共，和transformation 转换treatment 处理trimmed mean 截尾均值true value 真值t-test t检验two-tailed test 双侧检验Uunbalanced 不平衡的unbiased estimation 无偏估计unbiasedness 无偏性uniform distribution 均匀分布Vvalue of estimator 估计值variable 变量variance 方差variance components 方差分量variance ratio 方差比various 不同的vector 向量Wweight 加权，权重weighted average 加权平均值within groups 组内的ZZ score Z分数Ⅱ.2 最优化方法词汇英汉对照表Aactive constraint 活动约束active set method 活动集法analytic gradient 解析梯度approximate 近似arbitrary 强制性的argument 变量attainment factor 达到因子Bbandwidth 带宽be equivalent to 等价于best-fit 最佳拟合bound 边界Ccoefficient 系数complex-value 复数值component 分量constant 常数constrained 有约束的constraint 约束constraint function 约束函数continuous 连续的converge 收敛cubic polynomialinterpolation method三次多项式插值法curve-fitting 曲线拟合Ddata-fitting 数据拟合default 默认的，默认的define 定义diagonal 对角的direct search method 直接搜索法direction of search 搜索方向discontinuous 不连续Eeigenvalue 特征值empty matrix 空矩阵equality 等式exceeded 溢出的Ffeasible 可行的feasible solution 可行解finite-difference 有限差分first-order 一阶GGauss-Newton method 高斯-牛顿法goal attainment problem 目标达到问题gradient 梯度gradient method 梯度法Hhandle 句柄Hessian matrix 海色矩阵Iindependent variables 独立变量inequality 不等式infeasibility 不可行性infeasible 不可行的initial feasible solution 初始可行解initialize 初始化inverse 逆invoke 激活iteration 迭代iteration 迭代JJacobian 雅可比矩阵LLagrange multiplier 拉格朗日乘子large-scale 大型的least square 最小二乘least squares sense 最小二乘意义上的Levenberg-Marquardtmethod列文伯格-马夸尔特法line search 一维搜索linear 线性的linear equality constraints线性等式约束linear programmingproblem 线性规划问题local solution 局部解Mmedium-scale 中型的minimize 最小化mixed quadratic and cubic polynomial interpolation and extrapolation method 混合二次、三次多项式内插、外插法multiobjective 多目标的Nnonlinear 非线性的norm 范数Oobjective function 目标函数observed data 测量数据optimization routine 优化过程optimize 优化optimizer 求解器over-determined system 超定系统Pparameter 参数partial derivatives 偏导数polynomial interpolation method多项式插值法Qquadratic 二次的quadratic interpolation method 二次内插法quadratic programming 二次规划Rreal-value 实数值residuals 残差robust 稳健的robustness 稳健性，鲁棒性Sscalar 标量semi-infinitely problem 半无限问题Sequential Quadratic Programming method序列二次规划法simplex search method 单纯形法solution 解sparse matrix 稀疏矩阵sparsity pattern 稀疏模式sparsity structure 稀疏结构starting point 初始点step length 步长subspace trust regionmethod 子空间置信域法sum-of-squares 平方和symmetric matrix 对称矩阵Ttermination message 终止信息termination tolerance 终止容限the exit condition 退出条件the method of steepestdescent 最速下降法transpose 转置Uunconstrained 无约束的under-determined system负定系统Vvariable 变量vector 矢量Wweighting matrix 加权矩阵Ⅱ.3 样条词汇英汉对照表Aapproximation 逼近array 数组a spline in b-form/b-splineb样条a spline of polynomial piece/ppform spline分段多项式样条Bbivariate spline function 二元样条函数break/breaks 断点Ccoefficient/coefficients 系数cubic interpolation 三次插值/三次内插cubic polynomial 三次多项式cubic smoothing spline 三次平滑样条cubic spline 三次样条cubic spline interpolation三次样条插值/三次样条内插curve 曲线Ddegree of freedom 自由度dimension 维数Eend conditions 约束条件Iinput argument 输入参数interpolation 插值/内插interval 取值区间Kknot/knots 节点Lleast-squaresapproximation 最小二乘拟合Mmultiplicity 重次multivariate function 多元函数Ooptional argument 可选参数order 阶次output argument 输出参数Ppoint/points 数据点Rrational spline 有理样条rounding error 舍入误差（相对误差）Sscalar 标量sequence 数列（数组）spline 样条spline approximation 样条逼近/样条拟合spline function 样条函数spline curve 样条曲线spline interpolation 样条插值/样条内插spline surface 样条曲面smoothing spline 平滑样条Ttolerance 允许精度Uunivariate function 一元函数Vvector 向量Wweight/weights 权重Ⅱ.4 偏微分方程数值解词汇英汉对照表Aabsolute error 绝对误差absolute tolerance 绝对容限adaptive mesh 适应性网格Bboundary condition 边界条件Ccontour plot 等值线图converge 收敛coordinate 坐标系Ddecomposed 分解的decomposed geometry matrix 分解几何矩阵diagonal matrix 对角矩阵Dirichlet boundary conditionsDirichlet边界条件Eeigenvalue 特征值elliptic 椭圆形的error estimate 误差估计exact solution 精确解Ggeneralized Neumann boundary condition推广的Neumann边界条件geometry 几何形状geometry descriptionmatrix 几何描述矩阵geometry matrix 几何矩阵graphical user interface（GUI）图形用户界面Hhyperbolic 双曲线的Iinitial mesh 初始网格Jjiggle 微调LLagrange multipliers 拉格朗日乘子Laplace equation 拉普拉斯方程linear interpolation 线性插值loop 循环Mmachine precision 机器精度mixed boundary condition混合边界条件NNeuman boundarycondition Neuman边界条件node point 节点nonlinear solver 非线性求解器normal vector 法向量PParabolic 抛物线型的partial differential equation偏微分方程plane strain 平面应变plane stress 平面应力Poisson's equation 泊松方程polygon 多边形positive definite 正定Qquality 质量Rrefined triangular mesh 加密的三角形网格relative tolerance 相对容限relative tolerance 相对容限residual 残差residual norm 残差范数Ssingular 奇异的sparce matrix 稀疏矩阵stiffness matrix 刚度矩阵subregion 子域Ttriangular mesh 三角形网格Uundetermined 未定的uniform refinement 均匀加密uniform triangle net 均匀三角形网络Wwave equation 波动方程Algebraic Equation代数方程Elementary Operations-Addition基础混算-加法ElementaryOperations-Subtaction基础混算-减法ElementaryOperations-Multiplication基础混算-乘法Elementary Operations-Division基础混算-除法Elementary Operation基础四则混算Decimal Operations 小数混算Fractional Operations分数混算Convert fractional no. intodecimal no.分数转小数Convert fractional no. intopercentage.分数转百分数Convert decimal no. intopercentage.小数转百分数Convert percentage into decimal no.百分数转小数Percentage百分数Numerals数字符号Common factors and multiples公因子及公倍数Sorting数字排序Area图形面积Perimeter图形周界Change Units : Time单位转换-时间Change Units : Weight 单位转换-重量Change Units :Length单位转换-长度Directed Numbers 有向数Fractional Operations 分数混算Decimal Operations 小数混算Convert fractional no. into decimal no.分数转小数Convert fractional no. into percentage.分数转百分数Convert decimal no. into percentage.小数转百分数Convert percentage into decimal no.百分数转小数Percentage百分数Indices指数Algebraic Substitution 代数代入Polynomials多项式Co-Geometry坐标几何学Solving Linear Equation解一元线性方程Solving Simultaneous Equation解联立方程Slope直线斜率Equation of Straight Line直线方程x-intercept ( Equation of St. Line )直线x轴截距y-intercept ( Equation of St. Line )直线y轴截距Factorization因式分解Quadratic Equation 二次方程x-intercept ( Quadratic Equation )二次曲线x轴截距Geometry几何学Inequalities不等式Rate and Ratio比和比例Bearing方位角Trigonometry三角学Probability概率Statistics-Graph统计学-统计图表Statistics-Measure of centraltendency统计学-量度集中趋势Salary Tax薪俸税Bridging Game汉英对对碰Indices指数Function函数Rate and Ratio比和比例Trigonometry三角学Inequalities不等式Linear Programming线性规划Co-Geometry坐标几何学Slope直线斜率Equation of Straight Line直线方程x-intercept ( Equation of St. Line )直线x轴截距y-intercept ( Equation of St. Line )直线y轴截距Factorization因式分解Quadratic Equation二次方程x-intercept ( Quadratic Equation )二次曲线x轴截距Method of Bisection分半方法Polynomials多项式Probability概率Statistics-Graph统计学-统计图表Statistics-Measure of centraltendency统计学-量度集中趋势Statistics-Measure of dispersion统计学-量度分布Statistics-Normal Distribution统计学-正态分布Surds根式Probability概率Statistics-Measure of dispersion统计学-量度离差Statistics-Normal Distribution统计学-正态分布Statistics-Binomial Distribution统计学Statistics-Poisson Distribution统计学Statistics-Geometric Distribution统计学Co-Geometry坐标几何学Sequence序列十万Hundred thousand三位数3-digit number千Thousand千万Ten million小数Decimal分子Numerator分母Denominator分数Fraction五位数5-digit number公因子Common factor公倍数Common multiple中国数字Chinese numeral平方Square平方根Square root古代计时工具Ancient timingdevice古代记时工具Ancienttime-recording device古代记数方法Ancient countingmethod古代数字Ancient numeral包含Grouping四位数4-digit number四则计算Mixed operations (Thefour operations)加Plus加法Addition加法交换性质Commutativeproperty of addition未知数Unknown百分数Percentage百万Million合成数Composite number多位数Large number因子Factor折扣Discount近似值Approximation阿拉伯数字Hindu-Arabic numeral定价Marked price括号Bracket计算器Calculator差Difference真分数Proper fraction退位Decomposition除Divide除法Division除数Divisor乘Multiply乘法Multiplication乘法交换性质Commutative property of multiplication乘法表Multiplication table乘法结合性质Associative property of multiplication被除数Dividend珠算Computation using Chinese abacus倍数Multiple假分数Improper fraction带分数mixed number现代计算工具Modern calculating devices售价Selling price万Ten thousand最大公因子Highest Common Factor (H.C.F.)最小公倍数Lowest Common Multiple (L.C.M.)减Minus / Subtract减少Decrease减法Subtraction等分Sharing 等于Equal进位Carrying短除法Short division单数Odd number循环小数Recurring decimal零Zero算盘Chinese abacus亿Hundred million增加Increase质数Prime number积Product整除性Divisibility双数Even number罗马数字Roman numeral数学mathematics, maths(BrE),math(AmE)公理axiom定理theorem计算calculation运算operation证明prove假设hypothesis, hypotheses(pl.)命题proposition算术arithmetic加plus(prep.), add(v.),addition(n.)被加数augend, summand加数addend和sum减minus(prep.), subtract(v.),subtraction(n.)被减数minuend减数subtrahend差remainder乘times(prep.), multiply(v.),multiplication(n.)被乘数multiplicand, faciend乘数multiplicator积product除divided by(prep.), divide(v.),division(n.)被除数dividend除数divisor商quotient等于equals, is equal to, isequivalent to大于is greater than小于is lesser than大于等于is equal or greater than小于等于is equal or lesser than运算符operator平均数mean算术平均数arithmatic mean几何平均数geometric mean n个数之积的n次方根倒数（reciprocal）x的倒数为1/x有理数rational number无理数irrational number实数real number虚数imaginary number数字digit数number自然数natural number整数integer小数decimal小数点decimal point分数fraction分子numerator分母denominator比ratio正positive负negative零null, zero, nought, nil十进制decimal system二进制binary system十六进制hexadecimal system权weight, significance进位carry截尾truncation四舍五入round下舍入round down上舍入round up有效数字significant digit无效数字insignificant digit代数algebra公式formula, formulae(pl.)单项式monomial多项式polynomial, multinomial 系数coefficient未知数unknown, x-factor, y-factor, z-factor等式，方程式equation一次方程simple equation二次方程quadratic equation三次方程cubic equation四次方程quartic equation不等式inequation阶乘factorial对数logarithm指数，幂exponent乘方power二次方，平方square三次方，立方cube四次方the power of four, the fourth powern次方the power of n, the nth power开方evolution, extraction二次方根，平方根square root 三次方根，立方根cube root四次方根the root of four, the fourth rootn次方根the root of n, the nth rootsqrt(2)=1.414sqrt(3)=1.732sqrt(5)=2.236常量constant变量variable坐标系coordinates坐标轴x-axis, y-axis, z-axis横坐标x-coordinate纵坐标y-coordinate原点origin象限quadrant截距(有正负之分)intercede（方程的）解solution几何geometry点point线line面plane 体solid线段segment射线radial平行parallel相交intersect角angle角度degree弧度radian锐角acute angle直角right angle钝角obtuse angle平角straight angle周角perigon底base边side高height三角形triangle锐角三角形acute triangle直角三角形right triangle直角边leg斜边hypotenuse勾股定理Pythagorean theorem钝角三角形obtuse triangle不等边三角形scalene triangle等腰三角形isosceles triangle等边三角形equilateral triangle四边形quadrilateral平行四边形parallelogram矩形rectangle长length宽width周长perimeter面积area相似similar全等congruent三角trigonometry正弦sine余弦cosine正切tangent余切cotangent正割secant余割cosecant反正弦arc sine反余弦arc cosine反正切arc tangent反余切arc cotangent反正割arc secant反余割arc cosecant补充：集合aggregate元素element空集void子集subset交集intersection并集union补集complement映射mapping函数function定义域domain, field ofdefinition值域range单调性monotonicity奇偶性parity周期性periodicity图象image数列，级数series微积分calculus微分differential导数derivative极限limit无穷大infinite(a.) infinity(n.)无穷小infinitesimal积分integral定积分definite integral不定积分indefinite integral复数complex number矩阵matrix行列式determinant圆circle圆心centre(BrE), center(AmE)半径radius直径diameter圆周率pi弧arc半圆semicircle扇形sector环ring椭圆ellipse圆周circumference轨迹locus, loca(pl.)平行六面体parallelepiped立方体cube七面体heptahedron八面体octahedron九面体enneahedron十面体decahedron十一面体hendecahedron十二面体dodecahedron二十面体icosahedron多面体polyhedron旋转rotation轴axis球sphere半球hemisphere底面undersurface表面积surface area体积volume空间space双曲线hyperbola抛物线parabola四面体tetrahedron五面体pentahedron六面体hexahedron菱形rhomb, rhombus, rhombi(pl.), diamond正方形square梯形trapezoid直角梯形right trapezoid等腰梯形isosceles trapezoid五边形pentagon六边形hexagon七边形heptagon八边形octagon九边形enneagon十边形decagon十一边形hendecagon十二边形dodecagon多边形polygon正多边形equilateral polygon相位phase周期period振幅amplitude内心incentre(BrE), incenter(AmE)外心excentre(BrE),excenter(AmE)旁心escentre(BrE),escenter(AmE)垂心orthocentre(BrE),orthocenter(AmE)重心barycentre(BrE),barycenter(AmE)内切圆inscribed circle外切圆circumcircle统计statistics平均数average加权平均数weighted average方差variance标准差root-mean-squaredeviation, standard deviation比例propotion百分比percent百分点percentage百分位数percentile排列permutation组合combination概率，或然率probability分布distribution正态分布normal distribution非正态分布abnormaldistribution图表graph条形统计图bar graph柱形统计图histogram折线统计图broken line graph曲线统计图curve diagram扇形统计图pie diagramEnglish Chineseabbreviation 简写符号；简写abscissa 横坐标absolute complement 绝对补集absolute error 绝对误差absolute inequality 绝不等式absolute maximum 绝对极大值absolute minimum 绝对极小值absolute monotonic 绝对单调absolute value 绝对值accelerate 加速acceleration 加速度acceleration due to gravity 重力加速度; 地心加速度accumulation 累积accumulative 累积的accuracy 准确度act on 施于action 作用; 作用力acute angle 锐角acute-angled triangle 锐角三角形add 加addition 加法addition formula 加法公式addition law 加法定律addition law(of probability) （概率）加法定律additive inverse 加法逆元; 加法反元additive property 可加性adjacent angle 邻角adjacent side 邻边adjoint matrix 伴随矩阵algebra 代数algebraic 代数的algebraic equation 代数方程algebraic expression 代数式algebraic fraction 代数分式；代数分数式algebraic inequality 代数不等式algebraic number 代数数algebraic operation 代数运算algebraically closed 代数封闭algorithm 算法系统; 规则系统alternate angle （交）错角alternate segment 内错弓形alternating series 交错级数alternative hypothesis 择一假设;备择假设; 另一假设altitude 高；高度；顶垂线；高线ambiguous case 两义情况；二义情况amount 本利和；总数analysis 分析；解析analytic geometry 解析几何angle 角angle at the centre 圆心角angle at the circumference 圆周角angle between a line and a plane 直 与平面的交角angle between two planes 两平面的交角angle bisection 角平分angle bisector 角平分线 ；分角线angle in the alternate segment 交错弓形的圆周角angle in the same segment 同弓形内的圆周角angle of depression 俯角angle of elevation 仰角angle of friction 静摩擦角; 极限角angle of greatest slope 最大斜率的角angle of inclination 倾斜角angle of intersection 相交角；交角angle of projection 投射角angle of rotation 旋转角angle of the sector 扇形角angle sum of a triangle 三角形内角和angles at a point 同顶角angular displacement 角移位angular momentum 角动量angular motion 角运动angular velocity 角速度annum(X% per annum) 年（年利率X%）anti-clockwise direction 逆时针方向；返时针方向anti-clockwise moment 逆时针力矩anti-derivative 反导数; 反微商anti-logarithm 逆对数；反对数anti-symmetric 反对称apex 顶点approach 接近；趋近approximate value 近似值approximation 近似；略计；逼近Arabic system 阿刺伯数字系统arbitrary 任意arbitrary constant 任意常数arc 弧arc length 弧长arc-cosine function 反余弦函数arc-sin function 反正弦函数arc-tangent function 反正切函数area 面积Argand diagram 阿根图, 阿氏图argument (1)论证; (2)辐角argument of a complex number 复数的辐角argument of a function 函数的自变量arithmetic 算术arithmetic mean 算术平均；等差中顶；算术中顶arithmetic progression 算术级数；等差级数arithmetic sequence 等差序列arithmetic series 等差级数arm 边array 数组; 数组arrow 前号ascending order 递升序ascending powers of X X 的升幂assertion 断语; 断定associative law 结合律assumed mean 假定平均数assumption 假定；假设asymmetrical 非对称asymptote 渐近asymptotic error constant 渐近误差常数at rest 静止augmented matrix 增广矩阵auxiliary angle 辅助角auxiliary circle 辅助圆auxiliary equation 辅助方程average 平均；平均数；平均值average speed 平均速率axiom 公理axiom of existence 存在公理axiom of extension 延伸公理axiom of inclusion 包含公理axiom of pairing 配对公理axiom of power 幂集公理axiom of specification 分类公理axiomatic theory of probability 概率公理论axis 轴axis of parabola 拋物线的轴axis of revolution 旋转轴axis of rotation 旋转轴axis of symmetry 对称轴back substitution 回代bar chart 棒形图；条线图；条形图；线条图base （1）底；（2）基；基数base angle 底角base area 底面base line 底线base number 底数；基数base of logarithm 对数的底basis 基Bayes' theorem 贝叶斯定理bearing 方位（角）；角方向（角）bell-shaped curve 钟形图belong to 属于Bernoulli distribution 伯努利分布Bernoulli trials 伯努利试验bias 偏差；偏倚biconditional 双修件式; 双修件句bijection 对射; 双射; 单满射bijective function 对射函数; 只射函数billion 十亿bimodal distribution 双峰分布binary number 二进数binary operation 二元运算binary scale 二进法binary system 二进制binomial 二项式binomial distribution 二项分布binomial expression 二项式binomial series 二项级数binomial theorem 二项式定理bisect 平分；等分bisection method 分半法；分半方法bisector 等分线 ；平分线Boolean algebra 布尔代数boundary condition 边界条件boundary line 界（线）；边界bounded 有界的bounded above 有上界的；上有界的bounded below 有下界的；下有界的bounded function 有界函数bounded sequence 有界序列brace 大括号bracket 括号breadth 阔度broken line graph 折线图calculation 计算calculator 计算器；计算器calculus (1) 微积分学; (2) 演算cancel 消法；相消canellation law 消去律canonical 典型; 标准capacity 容量cardioid 心脏Cartesian coordinates 笛卡儿坐标Cartesian equation 笛卡儿方程Cartesian plane 笛卡儿平面Cartesian product 笛卡儿积category 类型；范畴catenary 悬链Cauchy sequence 柯西序列Cauchy's principal value 柯西主值Cauchy-Schwarz inequality 柯西- 许瓦尔兹不等式central limit theorem 中心极限定理central line 中线central tendency 集中趋centre 中心；心centre of a circle 圆心centre of gravity 重心centre of mass 质量中心centrifugal force 离心力centripedal acceleration 向心加速度centripedal force force 向心力centroid 形心；距心certain event 必然事件chain rule 链式法则chance 机会change of axes 坐标轴的变换change of base 基的变换change of coordinates 坐标轴的变换change of subject 主项变换change of variable 换元；变量的换characteristic equation 特征(征)方程characteristic function 特征(征)函数characteristic of logarithm 对数的首数; 对数的定位部characteristic root 特征(征)根chart 图；图表check digit 检验数位checking 验算chord 弦chord of contact 切点弦circle 圆circular 圆形；圆的circular function 圆函数；三角函数circular measure 弧度法circular motion 圆周运动circular permutation 环形排列;圆形排列; 循环排列circumcentre 外心；外接圆心circumcircle 外接圆circumference 圆周circumradius 外接圆半径circumscribed circle 外接圆cissoid 蔓叶class 区；组；类class boundary 组界class interval 组区间；组距class limit 组限；区限class mark 组中点；区中点classical theory of probability 古典概率论classification 分类clnometer 测斜仪clockwise direction 顺时针方向clockwise moment 顺时针力矩closed convex region 闭凸区域closed interval 闭区间coaxial 共轴coaxial circles 共轴圆coaxial system 共轴系coded data 编码数据coding method 编码法co-domain 上域coefficient 系数coefficient of friction 摩擦系数coefficient of restitution 碰撞系数; 恢复系数coefficient of variation 变差系数cofactor 余因子; 余因式cofactor matrix 列矩阵coincide 迭合；重合collection of terms 并项collinear 共线collinear planes 共线面collision 碰撞column (1)列；纵行；(2) 柱column matrix 列矩阵column vector 列向量combination 组合common chord 公弦common denominator 同分母；公分母common difference 公差。

a r X i v :q u a n t -p h /0102108v 2 9 O c t 2001Quantum Kolmogorov Complexity Based onClassical DescriptionsPaul M.B.Vit´a nyiAbstract —We develop a theory of the algorithmic informa-tion in bits contained in an individual pure quantum state.This extends classical Kolmogorov complexity to the quan-tum domain retaining classical descriptions.Quantum Kol-mogorov complexity coincides with the classical Kolmogorov complexity on the classical domain.Quantum Kolmogorov complexity is upper bounded and can be effectively approx-imated from above under certain conditions.With high probability a quantum object is incompressible.Upper-and lower bounds of the quantum complexity of multiple copies of individual pure quantum states are derived and may shed some light on the no-cloning properties of quantum states.In the quantum situation complexity is not sub-additive.We discuss some relations with “no-cloning”and “approximate cloning”properties.Keywords —Algorithmic information theory,quantum;classical descriptions of quantum states;information the-ory,quantum;Kolmogorov complexity,quantum;quantum cloning.I.IntroductionQUANTUM information theory,the quantum mechan-ical analogue of classical information theory [6],is ex-periencing a renaissance [2]due to the rising interest in the notion of quantum computation and the possibility of re-alizing a quantum computer [16].While Kolmogorov com-plexity [12]is the accepted absolute measure of information content in a individual classical finite object,a similar ab-solute notion is needed for the information content of an individual pure quantum state.One motivation is to extend probabilistic quantum information theory to Kolmogorov’s absolute individual notion.Another reason is to try and duplicate the success of classical Kolmogorov complexity as a general proof method in applications ranging from com-binatorics to the analysis of algorithms,and from pattern recognition to learning theory [13].We propose a theory of quantum Kolmogorov complexity based on classical de-scriptions and derive the results given in the abstract.A preliminary partial version appeared as [19].What are the problems and choices to be made develop-ing a theory of quantum Kolmogorov complexity?Quan-tum theory assumes that every complex vector of unit length represents a realizable pure quantum state [17].There arises the question of how to design the equipment that prepares such a pure state.While there are contin-uously many pure states in a finite-dimensional complexPartially supported by the EU fifth framework project QAIP,IST–1999–11234,the NoE QUIPROCONE IST–1999–29064,the ESF QiT Programmme,and the EU Fourth Framework BRA NeuroCOLT II Working Group EP 27150.Part of this work was done during the author’s 1998stay at Tokyo Institute of Technology,Tokyo,Japan,as Gaikoku-Jin Kenkyuin at INCOCSAT,and appeared in a preliminary version [19]archived as quant-ph/9907035.Address:CWI,Kruislaan 413,1098SJ Amsterdam,The Netherlands.Email:paulv@cwi.nlvector space—corresponding to all vectors of unit length—we can finitely describe only a countable subset.Imposing effectiveness on such descriptions leads to constructive pro-cedures.The most general such procedures satisfying uni-versally agreed-upon logical principles of effectiveness are quantum Turing machines,[3].To define quantum Kol-mogorov complexity by way of quantum Turing machines leaves essentially two options:1.We want to describe every quantum superposition ex-actly;or2.we want to take into account the number of bits/qubits in the specification as well the accuracy of the quantum state produced.We have to deal with three problems:•There are continuously many quantum Turing machines;•There are continuously many pure quantum states;•There are continuously many qubit descriptions.There are uncountably many quantum Turing machines only if we allow arbitrary real rotations in the definition of machines.Then,a quantum Turing machine can only be universal in the sense that it can approximate the compu-tation of an arbitrary machine,[3].In descriptions using universal quantum Turing machines we would have to ac-count for the closeness of approximation,the number of steps required to get this precision,and the like.In con-trast,if we fix the rotation of all contemplated machines to a single primitive rotation θwith cos θ=35,then there are only countably many Turing machines and the universal machine simulates the others exactly [1].Ev-ery quantum Turing machine computation,using arbitrary real rotations to obtain a target pure quantum state,can be approximated to every precision by machines with fixed rotation θbut in general cannot be simulated exactly—just like in the case of the simulation of arbitrary quantum Turing machines by a universal quantum Turing machine.Since exact simulation is impossible by a fixed universal quantum Turing machine anyhow,but arbitrarily close ap-proximations are possible by Turing machines using a fixed rotation like θ,we are motivated to fix Q 1,Q 2,...as a stan-dard enumeration of quantum Turing machines using only rotation θ.Our next question is whether we want programs (descrip-tions)to be in classical bits or in qubits?The intuitive no-tion of computability requires the programs to be ly,to prepare a quantum state requires a physical ap-paratus that “computes”this quantum state from classical specifications.Since such specifications have effective de-scriptions,every quantum state that can be prepared can be described effectively in descriptions consisting of classi-cal bits.Descriptions consisting of arbitrary pure quantumstates allows noncomputable(or hard to compute)informa-tion to be hidden in the bits of the amplitudes.In Defini-tion4we call a pure quantum state directly computable if there is a(classical)program such that the universal quan-tum Turing machine computes that state from the program and then halts in an appropriate fashion.In a computa-tional setting we naturally require that directly computable pure quantum states can be prepared.By repeating the preparation we can obtain arbitrarily many copies of the pure quantum state.If descriptions are not effective then we are not going to use them in our algorithms except possibly on inputs from an“unprepared”origin.Every quantum state used in a quantum computation arises from some classically prepa-ration or is possibly captured from some unknown origin. If the latter,then we can consume it as conditional side-information or an oracle.Restricting ourselves to an effective enumeration of quan-tum Turing machines and classical descriptions to describe by approximation continuously many pure quantum states is reminiscent of the construction of continuously many real numbers from Cauchy sequences of rational numbers,the rationals being effectively enumerable.Kolmogorov complexity:We summarize some basic definitions in Appendix A(see also this journal[20])in order to establish notations and recall the notion of short-est effective descriptions.More details can be found in the textbook[13].Shortest effective descriptions are“effective”in the sense that they are programs:we can compute the described objects from them.Unfortunately,[12],there is no algorithm that computes the shortest program and then halts,that is,there is no general method to compute the length of a shortest description(the Kolmogorov com-plexity)from the object being described.This obviously impedes actual use.Instead,one needs to consider com-putable approximations to shortest descriptions,for exam-ple by restricting the allowable approximation time.Apart from computability and approximability,there is another property of descriptions that is important to us.A set of descriptions is prefix-free if no description is a proper prefix of another description.Such a set is called a prefix code. Since a code message consists of concatenated code words, we have to parse it into its constituent code words to re-trieve the encoded source message.If the code is uniquely decodable,then every code message can be decoded in only one way.The importance of prefix-codes stems from the fact that(i)they are uniquely decodable from left to right without backing up,and(ii)for every uniquely decodable code there is a prefix code with the same length code words. Therefore,we can restrict ourselves to prefix codes.In our setting we require the set of programs to be prefix-free and hence to be a prefix-code for the objects being described.It is well-known that with every prefix-code there corresponds a probability distribution P(·)such that the prefix-code is a Shannon-Fano code1that assigns prefix code length l x=−log P(x)to x—irrespective of the regularities in x. 1In what follows,“log”denotes the binary logarithm.For example,with the uniform distribution P(x)=2−n on the set of n-bit source words,the Shannon-Fano code word length of an all-zero source word equals the code word length of a truly irregular source word.The Shannon-Fano code gives an expected code word length close to the en-tropy,and,by Shannon’s Noiseless Coding Theorem,it possesses the optimal expected code word length.But the Shannon-Fano code is not optimal for individual elements: it does not take advantage of the regularity in some ele-ments to encode those shorter.In contrast,one can view the Kolmogorov complexity K(x)as the code word length of the shortest program x∗for x,the set of shortest pro-grams consitituting the Shannon-Fano code of the so-called “universal distribution”m(x)=2−K(x).The code consist-ing of the shortest programs has the remarkable property that it achieves(i)an expected code length that is about optimal since it is close to the entropy,and simultaneously, (ii)every individual object is coded as short as is effectively possible,that is,squeezing out all regularity.In this sense the set of shortest programs constitutes the optimal effec-tive Shannon-Fano code,induced by the optimal effective distribution(the universal distribution).Quantum Computing:We summarize some basic def-initions in Appendix B in order to establish notations and briefly review the notion of a quantum Turing machine computation.See also this journal’s survey[2]on quan-tum information theory.More details can be found in the textbook[16].Loosely speaking,like randomized compu-tation is a generalization of deterministic computation,so is quantum computation a generalization of randomized computation.Realizing a mathematical random source to drive a random computation is,in its ideal form,presum-ably impossible(or impossible to certify)in practice.Thus, in applications an algorithmic random number generator is used.Strictly speaking this invalidates the analysis based on mathematical randomized computation.As John von Neumann[15]put it:“Any one who considers arithmetical methods of producing random digits is,of course,in a state of sin.For,as has been pointed out several times,there is no such thing as a random number—there are only meth-ods to produce random numbers,and a strict arithmetical procedure is of course not such a method.”In practice ran-domized computations reasonably satisfy theoretical anal-ysis.In the quantum computation setting,the practical problem is that the ideal coherent superposition cannot re-ally be maintained during computation but deteriorates—it decoheres.In our analysis we abstract from that problem and one hopes that in practice anti-decoherence techniques will suffice to approximate the idealized performance suffi-ciently.We view a quantum Turing machine as a generalization of the classic probabilistic(that is,randomized)Turing machine.The probabilistic Turing machine computation follows multiple computation paths in parallel,each path with a certain associated probability.The quantum Turing machine computation follows multiple computation paths in parallel,but now every path has an associated complex probability amplitude.If it is possible to reach the sameVIT´ANYI:QUANTUM KOLMOGOROV COMPLEXITY BASED ON CLASSICAL DESCRIPTIONS3state via different paths,then in the probabilistic case the probability of observing that state is simply the sum of the path probabilities.In the quantum case it is the squared norm of the summed path probability amplitudes.Since the probability amplitudes can be of opposite sign,the ob-servation probability can vanish;if the path probability amplitudes are of equal sign then the observation probabil-ity can get boosted since it is the square of the sum norm. While this generalizes the probabilistic aspect,and boosts the computation power through the phenomenon of inter-ference between parallel computation paths,there are extra restrictions vis-a-vis probabilistic computation in that the quantum evolution must be unitary.Quantum Kolmogorov Complexity:We define the Kolmogorov complexity of a pure quantum state as the length of the shortest two-part code consisting of a classical program to compute an approximate pure quantum state and the negative log-fidelity of the approximation to the target quantum state.We show that the resulting quantum Kolmogorov complexity coincides with the classical self-delimiting complexity on the domain of classical objects; and that certain properties that we love and cherish in the classical Kolmogorov complexity are shared by the new quantum Kolmogorov complexity:quantum Kolmogorov complexity of an n-qubit object is upper bounded by about 2n;it is not computable but can under certain conditions be approximated from above by a computable process;and with high probability a quantum object is incompressible. We may call this quantum Kolmogorov complexity the bit complexity of a pure quantum state|φ (using Dirac’s“ket”notation)and denote it by K(|φ ).From now on,we will denote by+<an inequality to within an additive constant, and by+=the situation when both+<and+>hold.For exam-ple,we will show that,for n-qubit states|φ ,the complexity satisfies K(|φ |n)+<2n.For certain restricted pure quan-tum states,quantum kolmogorov complexity satisfies the sub-additive property:K(|φ,ψ )+<K(|φ )+K(|ψ ||φ ). But,in general,quantum Kolmogorov complexity is not sub-additive.Although“cloning”of non-orthogonal states is forbidden in the quantum setting[21],[7],m copies of the same quantum state have combined complexity that can be considerable lower than m times the complexity of a single copy.In fact,quantum Kolmogorov complex-ity appears to enable us to express and partially quantify “non-clonability”and“approximate clonability”of individ-ual pure quantum states.Related Work:In the classical situation there are sev-eral variants of Kolmogorov complexity that are very mean-ingful in their respective settings:plain Kolmogorov com-plexity,prefix complexity,monotone complexity,uniform complexity,negative logarithm of universal measure,and so on[13].It is therefore not surprising that in the more com-plicated situation of quantum information several different choices of complexity can be meaningful and unavoidable in different settings.Following the preliminary version[19] of this work there have been alternative proposals:Qubit Descriptions:The most straightforward way to define a notion of quantum Kolmogorov complexity is to consider the shortest effective qubit description of a pure quantum state which is studied in[4].(This qubit com-plexity can also be formulated in terms of the conditional version of bit complexity as in[19].)An advantage of qubit complexity is that the upper bound on the complexity of a pure quantum state is immediately given by the number of qubits involved in the literal description of that pure quan-tum state.Let us denote the resulting qubit complexity of a pure quantum state|φ by KQ(|φ ).While it is clear that(just as with the previous aproach) the qubit complexity is not computable,it is unlikely that one can approximate the qubit complexity from above by a computable process in some meaningful sense.In particu-lar,the dovetailing approach we used in our approach now doesn’t seem applicable due to the non-countability of the potentential qubit program candidates.The quantitative incompressibility properties are much like the classical case (this is important for future applications).There are some interesting exceptions in case of objects consisting of multi-ple copies related to the“no-cloning”property of quantum objects,[21],[7].Qubit complexity does not satisfy the sub-additive property,and a certain version of it(bounded fidelity)is bounded above by the von Neumann entropy. Density Matrices:In classical algorithmic informa-tion theory it turns out that the negative logarithm of the “largest”probability distribution effectively approximable from below—the universal distribution—coincides with the self-delimiting Kolmogorov complexity.In[8]G´a cs defines two notions of complexities based on the negative loga-rithm of the“largest”density matrixµeffectively approx-imable from below.There arise two different complexi-ties of|φ based on whether we take the logarithm inside as KG(|φ )=− φ|logµ|φ or outside as Kg(|φ )=−log φ|µ|φ .It turns out that Kg(|φ )+<KG(|φ ). This approach serves to compare the two approaches above: It was shown that Kg(|φ )is within a factor four of K(|φ ); that KG(|φ )essentially is a lower bound on KQ(|φ )and an oracle version of KG is essentially an upper bound on qubit complexity KQ.Since qubit complexity is trivially+<n and it was shown that bit complexity is typically close to2n,atfirst glance this leaves the possibility that the two complexities are within a factor two of each other.This turns out to be not the case since it was shown that the Kg complexity can for some arguments be much smaller than the KG complexity,so that the bit complexity is in these cases also much smaller than the qubit complexity.As[8] states:this is due to the permissive way the bit complexity deals with approximation.The von Neumann entropy of a computable density matrix is within an additive constant (the complexity of the program computing the density ma-trix)of a notion of average complexity.The drawback of density matrix based complexity is that we seem to have lost the direct relation with a meaningful interpretation in terms of description length:a crucial aspect of classical Kolmogorov complexity in most applications[13].Real Descriptions:A version of quantum Kolmogorov4IEEE TRANSACTIONS ON INFORMATION THEORYcomplexity briefly considered in[19]uses computable real parameters to describe the pure quantum state with com-plex probability amplitudes.This requires two reals per complex probability amplitude,that is,for n qubits one requires2n+1real numbers in the worst case.A real num-ber is computable if there is afixed program that outputs consecutive bits of the binary expansion of the number for-ever.Since every computable real number may require a separate program,a computable n-qubit pure state may re-quire2n+1finite programs.Most n-qubit pure states have parameters that are noncomputable and increased preci-sion will require increasingly long programs.For exam-ple,if the parameters are recursively enumerable(the po-sitions of the“1”s in the binary expansion is a recursively enumerable set),then a log k length program per parame-ter,to achieve k bits precision per recursively enumerable real,is sufficient and for some recursively enumerable re-als also necessary.In certain contexts where the approx-imation of the real parameters is a central concern,such considerations may be useful.While this approach does not allow the development of a clean theory in the sense of the previous approaches,it can be directly developed in terms of algorithmic thermodynamics—an extension of Kolmogorov complexity to randomness of infinite sequences (such as binary expansions of real numbers)in terms of coarse-graining and sequential Martin-L¨o f tests,analogous to the classical case in[9],[13].But this is outside the scope of the present paper.II.Quantum Turing Machine ModelWe assume the notation and definitions in Appendices A, B.Our model of computation is a quantum Turing ma-chine equipped with a input tape that is one-way infinite with the classical input(the program)in binary left ad-justed from the beginning.We require that the input tape is read-only from left-to-right without backing up.This automatically yields a property we require in the sequel: The set of halting programs is prefix-free.Additionaly,the machine contains a one-way infinite work tape containing qubits,a one-way infinite auxiliary tape containing qubits, and a one-way infinite output tape containing qubits.Ini-tially,the input tape contains a classical binary program p, and all(qu)bits of the work tape,auxiliary tape,and out-put tape qubits are set to|0 .In case the Turing machine has an auxiliary input(classical or quantum)then initially the leftmost qubits of the auxiliary tape contain this in-put.A quantum Turing machine Q with classical program p and auxiliary input y computes until it halts with output Q(p,y)on its output tape or it computes forever.Halt-ing is a more complicated matter here than in the classical case since quantum Turing machines are reversible,which means that there must be an ongoing evolution with non-repeating configurations.There are various ways to resolve this problem[3]and we do not discuss this matter further. We only consider quantum Turing machine that do not modify the output tape after halting.Another—related—problem is that after halting the quantum state on the out-put tape may be“entangled”with the quantum state of the remainder of the machine,that is,the input tape,thefinite control,the work tape,and the auxilliary tape.This hasthe effect that the output state viewed in isolation may notbe a pure quantum state but a mixture of pure quantumstates.This problem does not arise if the output and the remainder of the machine form a tensor product so that theoutput is un-entangled with the remainder.The results inthis paper are invariant under these different assumptions,but considering output entangled with the remainder ofthe machine complicates formulas and calculations.Corre-spondingly,we restrict consideration to outputs that forma tensor product with the remainder of the machine,withthe understanding that the same results hold with aboutthe same proofs if we choose the other option—except inthe case of Theorem4item(ii),see the pertinent caveat there.Note that the Kolmogorov complexity based on en-tangled output tapes is at most(and conceivably less than)the Kolmogorov complexity based on un-entangled outputtapes.Definition1:Define the output Q(p,y)of a quantumTuring machine Q with classical program p and auxil-iary input y as the pure quantum state|ψ resulting of Q computing until it halts with output|ψ on its ouputtape.Moreover,|ψ doesn’t change after halting,andit is un-entangled with the remainder of Q’s configura-tion.We write Q(p,y)<∞.If there is no such|ψthen Q(p,y)is undefined and we write Q(p,y)=∞.By definition the input tape is read-only from left-to-rightwithout backing up:therefore the set of halting programsP y={p:Q(p,y)<∞}is prefix-free:no program in P y is a proper prefix of another program in P y.Put differ-ently,the Turing machine scans all of a halting program p but never scans the bit following the last bit of p:it isself-delimiting.Wefix the rotation of all contemplated machines to a sin-gle primitive rotationθwith cosθ=35.Thereare only countably many such Turing ing astandard ordering,wefix Q1,Q2,...as a standard enumer-ation of quantum Turing machines using only rotationθ. By[1],there is a universal machine U in this enumeration that simulates the others exactly:U(1i0p,y)=Q i(p,y), for all i,p,y.(Instead of the many-bit encoding1i0for i we can use a shorter self-delimiting code like i′in Ap-pendix A.)As noted in the Introduction,every quantum Turing machine computation using arbitrary real rotations can be approximated to arbitrary precision by machines withfixed rotationθbut in general cannot be simulated exactly.Remark1:There are two possible interpretations for the computation relation Q(p,y)=|x .In the narrow interpre-tation we require that Q with p on the input tape and y on the conditional tape halts with|x on the output tape.In the wide interpretation we can define pure quantum states by requiring that for every precision parameter k>0the computation of Q with p on the input tape and y on the conditional tape,with k on a special new tape where the precision is to be supplied,halts with|x′ on the output tape and|| x|x′ ||2≥1−1/2k.Such a notion of“com-VIT ´ANYI:QUANTUM KOLMOGOROV COMPLEXITY BASED ON CLASSICAL DESCRIPTIONS5putable”or “recursive”pure quantum states is similar to Turing’s notion of “computable numbers.”In the remain-der of this section we use the narrow interpretation.Remark 2:As remarked in [8],the notion of a quan-tum computer is not essential to the theory here or in [4],[8].Since the computation time of the machine is not limited in the theory of description complexity as de-veloped here,a quantum computer can be simulated by a classical computer to every desired degree of precision.We can rephrase everything in terms of the standard enu-meration of T 1,T 2,...of classical Turing machines.Let |x = N −1i =0αi |e i (N =2n )be an n -qubit state.We can write T (p )=|x if T either outputs(i)algebraic definitions of the coefficients of |x (in case these are algebraic),or(ii)a sequence of approximations (α0,k ,...,αN −1,k )for k =1,2,...where αi,k is an algebraic approximation of αi to within 2−k .III.Classical Descriptions of Pure QuantumStates The complex quantity x |z is the inner product of vec-tors x |and |z .Since pure quantum states |x ,|z have unit length,|| x |z ||=|cos θ|where θis the angle between vectors |x and |z .The quantity || x |z ||2,the fidelity between |x and |z ,is a measure of how “close”or “con-fusable”the vectors |x and |z are.It is the probability of outcome |x being measured from state |z .Essentially,we project |z on outcome |x using projection |x x |resulting in x |z |x .Definition 2:The (self-delimiting)complexity of |x with respect to quantum Turing machine Q with y as conditional input given for free isK Q (|x |y )=min p{l (p )+⌈−log || z |x ||2⌉:Q (p,y )=|z }(1)where l (p )is the number of bits in the program p ,auxiliary y is an input (possibly quantum)state,and |x is the target state that one is trying to describe.Note that |z is the quantum state produced by the com-putation Q (p,y ),and therefore,given Q and y ,completely determined by p .Therefore,we obtain the minimum of the right-hand side of the equality by minimizing over p only.We call the |z that minimizes the right-hand sidethe directly computed part of |x while ⌈−log || z |x ||2⌉is the approximation part .Quantum Kolmogorov complexity is the sum of two terms:the first term is the integral length of a binary pro-gram,and the second term,the minlog probability term,corresponds to the length of the corresponding code word in the Shannon-Fano code associated with that probabil-ity distribution,see for example [6],and is thus also ex-pressed in an integral number of bits.Let us consider this relation more closely:For a quantum system |z the quantity P (x )=|| z |x ||2is the probability that the system passes a test for |x ,and vice versa.The term ⌈−log || z |x ||2⌉can be viewed as the code word lengthto redescribe |x ,given |z and an orthonormal basis with |x as one of the basis vectors,using the Shannon-Fano pre-fix code.This works as follows:Write N =2n .For every state |z in (2n )-dimensional Hilbert space with basis vec-tors B ={|e 0 ,...,|e N −1 }we have N −1i =0|| e i |z ||2=1.If the basis has |x as one of the basis vectors,then we can consider |z as a random variable that assumes value |x with probability || x |z ||2.The Shannon-Fano code word for |x in the probabilistic ensemble B ,(|| e i |z ||2)iisbased on the probability || x |z ||2of |x ,given |z ,and haslength ⌈−log || x |z ||2⌉.Considering a canonical method of constructing an orthonormal basis B =|e 0 ,...,|e N −1 from a given basis vector,we can choose B such thatK (B )+=min i {K (|e i )}.The Shannon-Fano code is ap-propriate for our purpose since it is optimal in that it achieves the least expected code word length—the expec-tation taken over the probability of the source words—up to 1bit by Shannon’s Noiseless Coding Theorem.As in the classical case the quantum Kolmogorov complexity is an integral number.The main property required to be able to develop a meaningful theory is that our definition satisfies a so-called Invariance Theorem (see also Appendix A).Below we use “U ”to denote a special type of universal (quantum)Turing machine rather than a unitary matrix.Theorem 1(Invariance)There is a universal machine U ,such that for all machines Q ,there is a constant c Q (the length of the description of the index of Q in the enumera-tion),such that for all quantum states |x and all auxiliary inputs y we have:K U (|x |y )≤K Q (|x |y )+c Q .Proof:Assume that the program p that minimizes the right-hand side of (1)is p 0and the computed |z is |z 0 :K Q (|x |y )=l (p 0)+⌈−log || z 0|x ||2⌉.There is a universal quantum Turing machine U in the standard enumeration Q 1,Q 2,...such that for every quan-tum Turing machine Q in the enumeration there is a self-delimiting program i Q (the index of Q )and U (i Q p,y )=Q (p,y )for all p,y :if Q (p,y )=|z then U (i Q p,y )=|z .In particular,this holds for p 0such that Q with auxiliary input y halts with output |z 0 .But U with auxiliary input y halts on input i Q p 0also with output |z 0 .Consequently,the program q that minimizes the right-hand side of (1)with U substituted for Q ,and computes U (q,y )=|u for some state |u possibly different from |z ,satisfiesK U (|x |y )=l (q )+⌈−log || u |x ||2⌉≤l (i Q p 0)+⌈−log || z 0|x ||2⌉.Combining the two displayed inequalities,and setting c Q =l (i Q ),proves the theorem.。

㊃论 著㊃D O I :10.3969/j.i s s n .1672-9455.2023.13.004N L R ㊁P L R ㊁MH R 与颈动脉粥样硬化的关系研究*张 京1,朱 虹2ә,吴钦钦2,凃 乾11.江汉大学医学部,湖北武汉430056;2.湖北省武汉市中心医院全科医学科,湖北武汉430014摘 要:目的 探讨中性粒细胞与淋巴细胞比值(N L R )㊁血小板与淋巴细胞比值(P L R ),以及单核细胞与高密度脂蛋白胆固醇比值(MH R )与颈动脉粥样硬化(C A S )的关系㊂方法 回顾性分析武汉市中心医院604例住院患者的临床资料,根据颈动脉彩超检查结果分为颈动脉粥样硬化组(C A S 组)369例,非颈动脉粥样硬化组(非C A S 组)235例㊂采用受试者工作特征(R O C )曲线评价N L R ㊁P L R ㊁MH R 对C A S 的预测价值㊂采用二元L o g i s t i c 回归分析C A S 的危险因素㊂结果 单因素分析显示,C A S 组中男性㊁高脂血症㊁吸烟史㊁老年患者比例及白细胞计数(W B C )㊁低密度脂蛋白胆固醇(L D L -C )㊁空腹血糖(F P G )㊁N L R ㊁P L R ㊁MH R 均高于非C A S组(P <0.05);R O C 曲线分析显示,N L R ㊁P L R ㊁MH R 及N L R 联合P L R 预测C A S 的A U C 分别为0.792㊁0.704㊁0.631和0.803(P <0.05);二元L o g i s t i c 回归分析显示,N L R>1.98㊁P L R>105.8㊁MH R>0.31㊁L D L -C >3.10mm o l /L ㊁F P G>10.13mm o l /L ㊁老年是发生C A S 的独立危险因素(P <0.05)㊂结论 高水平N L R ㊁P L R ㊁MH R 可作为C A S 发生的危险因素,其中N L R ㊁P L R 有望成为C A S 的预测指标,二者联合预测效能更高㊂关键词:颈动脉粥样硬化; 中性粒细胞与淋巴细胞比值; 血小板与淋巴细胞比值; 单核细胞与高密度脂蛋白胆固醇比值中图法分类号:R 543.4文献标志码:A文章编号:1672-9455(2023)13-1841-05R e l a t i o n s h i p be t w e e n N L R ,P L R a n d MH R w i t h c a r o t i d a t h e r o s c l e r o s i s *Z HA N G J i n g 1,Z HU H o n g 2ә,WU Q i n qi n 2,T U Q i a n 11.S c h o o l o f M e d i c i n e ,J i a n g h a n U n i v e r s i t y ,W u h a n ,H u b e i 430056,C h i n a ;2.D e p a r t m e n t o f G e n e r a l P r a c t i c e M e d i c i n e ,W u h a n M u n i c i p a l C e n t r a l H o s pi t a l ,W u h a n ,H u b e i 430014,C h i n a A b s t r a c t :O b je c t i v e T o i n v e s t i g a t e t h e r e l a t i o n s h i p b e t w e e n n e u t r o p h i l t o l y m p h o c y t e r a t i o (N L R ),p l a t e l e t t o l y m p h o c y t e r a t i o (P L R )a n d m o n o c y t e t o h i g h -d e n s i t y l i p o pr o t e i n r a t i o (MH R )w i t h c a r o t i d a t h e r -o s c l e r o s i s (C A S ).M e t h o d s T h e c l i n i c a l d a t a o f 604h o s p i t a l i z e d p a t i e n t s i n W u h a n M u n i c i p a l C e n t r a l H o s pi -t a l w e r e r e t r o s p e c t i v e l y a n a l y z e d ,i n c l u d i n g 369c a s e s i n t h e c a r o t i d a t h e r o s c l e r o s i s g r o u p (C A S g r o u p )a n d 235c a s e s i n t h e n o n -c a r o t i d a t h e r o s c l e r o s i s g r o u p (n o n -C A S g r o u p )a c c o r d i n g to t h e c a r o t i d a r t e r i a l c o l o r u l -t r a s o u n d r e s u l t s .T h e r e c e i v e r o p e r a t i o n c h a r a c t e r i s t i c (R O C )c u r v e w a s u s e d t o e v a l u a t e t h e p r e d i c t i v e v a l u e o f N L R ,P L R a n d MH R f o r c a r o t i d a t h e r o s c l e r o s i s .T h e b i n a r y L o g i s t i c r e g r e s s i o n w a s u s e d t o a n a l yz e t h e r i s k f a c t o r s o f C A S .R e s u l t s T h e u n i v a r i a t e a n a l y s i s s h o w e d t h a t t h e p r o p o r t i o n o f m a l e ,h y p e r l i p i d e m i a ,s m o k i n g h i s t o r y,e l d e r l y p a t i e n t s a n d W B C c o u n t (W B C ),L D L -C ,F P G ,N L R ,P L R a n d MH R i n t h e C A S g r o u p w e r e a l l h i gh e r t h a n t h o s e i n t h e n o n -C A S g r o u p (P <0.05);t h e R O C c u r v e a n a l ys i s s h o w e d t h a t t h e a r e a u n d e r t h e c u r v e (A U C )o f N L R ,P L R ,MH R a n d N L R c o m b i n e d w i t h P L R f o r p r e d i c t i n g CA S w e r e 0.792,0.704,0.631a n d 0.803r e s p e c t i v e l y (P <0.05);t h e b i n a r y L o g i s t i c r e g r e s s i o n a n a l ys i s s h o w e d t h a t N L R>1.98,P L R>105.8,MH R>0.31,L D L -C >3.10mm o l /L ,F P G>10.13mm o l /L a n d o l d a g e w e r e t h e i n d e pe n d e n t r i s kf a c t o r s f o r t h e o c c u r r e n c e (P <0.05).C o n c l u s i o n T h e h i gh l e v e l s o f N L R ,P L R ,a n d MH R c o u l d b e u s e d a s t h e r i s k f a c -t o r s f o r t h e C A S o c c u r r e n c e ,i n w h i c h N L R a n d P L R a r e e x p e c t e d t o b e c o m e t h e p r e d i c t i v e i n d i c a t o r s o f C A S ,a n d t h e c o m b i n e d p r e d i c t i v e e f f i c i e n c y o f t h e t w o i n d i c a t o r s i s h i gh e r .K e y wo r d s :c a r o t i d a t h e r o s c l e r o s i s ; n e u t r o p h i l t o l y m p h o c y t e r a t i o ; p l a t e l e t t o l y m p h o c y t e r a t i o ; m o n o c y t e t o h i g h -d e n s i t y l i p o pr o t e i n r a t i o ㊃1481㊃检验医学与临床2023年7月第20卷第13期 L a b M e d C l i n ,J u l y 2023,V o l .20,N o .13*基金项目:湖北省武汉市卫生健康委员会课题(WX 17Q 03)㊂ 作者简介:张京,女,医师,主要从事全科医学研究㊂ ә通信作者,E -m a i l :153********@163.c o m ㊂网络首发 h t t p s ://k n s .c n k i .n e t /k c m s 2/a r t i c l e /a b s t r a c t ?u r l I d =50.1167.R.20230316.1721.006&u n i pl a t f o r m=N Z K P T (2023-03-17)Copyright ©博看网. All Rights Reserved.动脉粥样硬化(A S)是缺血性卒中的重要病理基础,而颈动脉是A S最常累及的部位,当颈动脉粥样硬化(C A S)进展至颈动脉严重狭窄甚至闭塞㊁斑块脱落堵塞颅内血管时,会直接引起缺血性卒中㊂临床上出现脑缺血症状才来就诊的患者往往错过了治疗的最佳时机,甚至会导致不可逆转的后遗症㊂因此,寻找简单经济的检验指标用于早期诊断显得尤为重要㊂基础研究发现,当机体发生A S时,超敏C反应蛋白㊁白细胞介素-6㊁白细胞介素-1β㊁肿瘤坏死因子㊁血清淀粉样蛋白等传统的炎症指标水平显著升高[1],但因其检测费用较高㊁影响因素较多,未能在基层医院广泛开展㊂外周血炎症指标,如中性粒细胞与淋巴细胞比值(N L R)㊁血小板与淋巴细胞比值(P L R),以及与血脂代谢指标组合的单核细胞与高密度脂蛋白胆固醇比值(MH R)也能全面地反映机体的炎症水平,已被证实与缺血性卒中患者发生C A S密切相关[2-4]㊂而在临床工作中,医师更重视缺血性卒中的一级预防,旨在发病前对C A S这一危险因素进行干预与控制㊂因此,本研究选取高血压㊁2型糖尿病㊁高脂血症等常见慢性病患者,探索N L R㊁P L R㊁MH R与其发生C A S的相关性,以期为患者早期诊断提供新的临床参考指标,在早期识别卒中高危人群,减轻卒中带来的疾病负担㊂1资料与方法1.1一般资料本研究采用回顾性研究方法,连续选取2020年12月至2021年12月于武汉市中心医院进行颈动脉彩超检查的604例住院患者,按照彩超检查结果分为C A S组与非C A S组㊂纳入标准:(1)包含高血压㊁2型糖尿病㊁高脂血症任意一种诊断;(2)年龄40~70岁;(3)临床资料完整㊂排除标准:1型糖尿病㊁糖尿病急性并发症㊁继发性高血压㊁冠状动脉粥样硬化性心脏病㊁缺血性卒中㊁感染性疾病㊁免疫系统疾病㊁血液系统疾病㊁严重肝肾功能不全患者,近1周服用过抗血小板聚集药㊁抗菌药物㊁免疫抑制剂㊁避孕药㊁激素类药物者,近6个月内有外伤或外科手术史者,妊娠期或哺乳期女性㊂本研究经武汉市中心医院医学伦理委员会审查通过(伦理批号:WH Z X K Y L2022-075)㊂1.2方法1.2.1临床资料收集收集患者入院时的临床资料,包括年龄㊁性别㊁既往史(高血压㊁2型糖尿病㊁高脂血症等疾病史㊁手术史㊁用药史)㊁吸烟史㊁实验室检查结果㊂中年定义为年龄ȡ40岁且<60岁,老年定义为年龄ȡ60岁㊂吸烟定义为每天吸烟1支以上,连续或累计吸烟时长超过6个月㊂实验室检查指标标本为患者禁食8~10h后次日清晨采集的静脉血㊂采用S y s m e x X N-10分析仪检测血常规相关参数,包括白细胞计数(W B C)㊁中性粒细胞计数(N E)㊁淋巴细胞计数(L Y)㊁单核细胞计数(MO)㊁血小板计数(P L T)㊂使用O l y m p u s A U5421分析仪检测甘油三酯(T G)㊁总胆固醇(T C)㊁高密度脂蛋白胆固醇(H D L-C)㊁低密度脂蛋白胆固醇(L D L-C)㊁血清尿酸(U A)㊁血清肌酐(S C r)和空腹血糖(F P G)水平㊂N L R㊁P L R㊁MH R由以下公式计算:N L R=N E/L Y;P L R=P L T/L Y; MH R=MO/H D L-C㊂1.2.2颈动脉彩超评估颈动脉彩超由本院超声科具有副主任医师职称以上的医师进行评估,使用飞利浦I U-22型彩色多普勒超声诊断仪(L9-3MH z线阵探头,探头频率5~10MH z)对研究对象双侧颈动脉进行扫描㊂于受检者颈动脉分叉近端后壁约1.5c m 处测量颈动脉内膜-中膜厚度(c I MT),检测3次取平均值为最终结果㊂C A S为颈动脉内膜局限性增厚(1.0mmɤc I MT<1.5mm);C A S斑块为c I MTȡ1.5mm,或大于周围正常c I MT至少0.5mm,或局限性内膜增厚大于周围正常c I MT的50%,且有凸向管腔的局部结构变化㊂C A S组包括C A S与C A S斑块患者;非C A S组为c I MT正常(c I MT<1.0mm)且无C A S斑块患者㊂1.3统计学处理采用E x c e l2019软件进行数据采集,采用S P S S26.0统计软件进行数据处理㊂对计量资料进行K o l m o g o r o v-S m i r n o v检验,符合正态分布的计量资料以xʃs表示,两组间比较采用独立样本t 检验,不服从正态分布的计量资料以M(P25,P75)表示,两组间比较采用秩和检验;计数资料以例数或百分率表示,组间比较采用χ2检验;采用M e d c a l c20.0软件绘制受试者工作特征(R O C)曲线,评价指标的预测效能;采用二元L o g i s t i c回归分析影响C A S的危险因素㊂以P<0.05为差异有统计学意义㊂2结果2.1两组临床资料比较经颈动脉彩超评估,将604例患者分为C A S组369例,非C A S组235例㊂C A S 组与非C A S组相比,高血压㊁2型糖尿病患者所占比例,以及T C㊁T G㊁U A㊁S C r水平差异无统计学意义(P>0.05);C A S组的男性㊁高脂血症㊁吸烟史㊁老年患者比例,W B C㊁L D L-C㊁F P G㊁N L R㊁P L R㊁MH R高于非C A S组,而C A S组的H D L-C水平低于非C A S 组,差异均有统计学意义(P<0.05)㊂见表1㊂2.2各实验室指标预测C A S的效能比较以单因素分析中差异有统计学意义的实验室指标为检验变量,以是否发生C A S为状态变量,绘制R O C曲线㊂N L R㊁P L R㊁MH R㊁N L R联合P L R对C A S的预测效能比较:N L R联合P L R的曲线下面积(A U C)与N L R 接近(Z=1.610,P=0.107),N L R的A U C高于P L R㊁MH R(Z=3.675,P<0.001;Z=2.132,P= 0.033)㊂见表2㊁图1㊂㊃2481㊃检验医学与临床2023年7月第20卷第13期 L a b M e d C l i n,J u l y2023,V o l.20,N o.13Copyright©博看网. All Rights Reserved.表1 C A S 组与非C A S 组临床资料比较[n (%)或M (P 25,P 75)或x ʃs ]组别n男性高血压2型糖尿病高脂血症吸烟史老年C A S 组369201(54.47)199(53.93)279(75.61)238(64.50)97(26.29)144(39.02)非C A S 组23597(41.28)112(47.66)161(68.51)132(56.17)33(14.04)55(23.40)t /χ2/Z10.0002.2603.6584.19612.74415.856P0.0020.1330.0560.041<0.001<0.001组别W B C (ˑ109/L )T C (mm o l /L )T G (mm o l /L )L D L -C (mm o l /L )H D L -C (mm o l /L )U A (μm o l /L )C A S 组5.89(5.07,6.94)4.87(4.08,5.72)1.46(1.00,2.12)3.06ʃ0.961.11(0.94,1.32)338(281,408)非C A S 组5.56(4.84,6.54)4.64(4.04,5.58)1.49(1.01,2.54)2.81ʃ0.901.18(0.98,1.41)334(271,396)t /χ2/Z-2.340-1.266-0.5293.112-2.599-0.578P0.0190.2060.5960.0020.0090.563组别S C r (μm o l /L )F P G (mm o l /L )N L RP L RMH RC A S 组59.10(48.60,72.35)7.71(5.83,11.20)2.23(1.78,2.76)129.59(114.24,161.96)0.32(0.24,0.44)非C A S 组57.10(49.00,66.80)6.99(5.52,9.46)1.58(1.34,1.93)110.14(90.25,135.33)0.26(0.20,0.35)t /χ2/Z-1.665-3.085-12.120-8.479-5.407P0.0960.002<0.001<0.001<0.001表2 各实验室指标预测C A S 的效能比较指标A U C A U C 的95%C I c u t -o f f 值P灵敏度(%)特异度(%)约登指数N L R 0.7920.758~0.8241.98<0.00164.7778.300.431P L R0.7040.666~0.741105.80<0.00187.2646.810.341MH R 0.6310.591~0.6690.31<0.00152.0367.230.193N L R 联合P L R 0.8030.769~0.830-<0.00171.2771.910.432W B C0.5560.519~0.5975.56ˑ109/L0.01861.5250.640.122H D L -C0.5630.522~0.6031.35mm o l /L0.00979.4031.060.105L D L -C0.5760.535~0.6103.10mm o l /L0.00149.8667.660.175F P G0.5740.534~0.61410.13mm o l /L0.00229.8182.550.124注:-表示无数据㊂图1 各指标预测C A S 的R O C 曲线2.3 二元L o g i s t i c 回归分析发生C A S 的危险因素 以是否发生C A S 为因变量,以单因素分析中差异有统计学意义的指标为自变量,进行二元L o g i s t i c 回归分析,赋值见表3㊂结果显示,N L R>1.98㊁P L R>105.8㊁MH R>0.31㊁L D L -C>3.10mm o l /L ㊁F P G>10.13mm o l /L ㊁老年是发生C A S 的独立危险因素(P <0.05)㊂见表4㊂表3 二元L o gi s t i c 回归分析赋值表变量赋值C A S否=0,是=1N L R>1.98否=0,是=1P L R>105.8否=0,是=1MH R>0.31否=0,是=1W B C >5.56ˑ109/L否=0,是=1H D L -C <1.35mm o l /L否=0,是=1L D L -C >3.10mm o l /L否=0,是=1F P G>10.13mm o l /L否=0,是=1老年否=0,是=1男性否=0,是=1高脂血症否=0,是=1吸烟史否=0,是=1注:连续变量以R O C 曲线中c u t -o f f 值转换为二分类变量㊂㊃3481㊃检验医学与临床2023年7月第20卷第13期 L a b M e d C l i n ,J u l y 2023,V o l .20,N o .13Copyright ©博看网. All Rights Reserved.表4二元L o g i s t i c回归分析发生C A S的危险因素项目βS E W a l d sχ2P O R O R的95%C I N L R>1.981.4040.22040.671<0.0014.0702.64~6.27 P L R>105.81.8490.25253.809<0.0016.3513.88~10.41 MH R>0.310.6160.2575.7300.0171.8521.12~3.07 W B C>5.56ˑ109/L0.2160.2330.8660.3521.2420.79~1.96 H D L-C<1.35mm o l/L0.1610.2520.4070.5241.1740.72~1.92 L D L-C>3.10mm o l/L0.8980.23514.640<0.0012.4561.55~3.89 F P G>10.13mm o l/L0.7830.2589.1930.0022.1891.32~3.63老年1.0030.23518.154<0.0012.7261.72~4.32男性0.1210.2420.2520.6161.1290.70~1.81高脂血症-0.0520.2280.0520.8190.9490.61~1.48吸烟史0.3470.2901.4370.2311.4150.80~2.50常量-2.9320.36863.342<0.0010.053-注:-表示无数据㊂3讨论炎症反应是A S发生㊁发展中必不可少的环节[5]㊂全血细胞计数及血脂作为慢性病患者复查的基本检验项目在基层医院已得到广泛应用㊂N L R㊁P L R㊁MH R作为复合指标既可反映机体血管的炎症反应状态,又能避免单一细胞检测结果易受感染㊁脱水等情况影响的缺陷,已被证实与冠状动脉粥样硬化的发生㊁发展及患者预后密切相关[6-9]㊂本研究通过R O C 曲线分析发现,仅有N L R㊁P L R可作为C A S的独立预测因子,A U C均大于0.7,具有较高的诊断价值㊂MH R的A U C<0.7,说明其预测准确性较低㊂可能因为MH R值偏小,其变化差异也较小㊂而W B C㊁H D L-C㊁L D L-C㊁F P G的A U C接近0.5,预测价值低㊂通过二元L o g i s t i c回归分析发现,在控制H D L-C㊁W B C㊁性别㊁高脂血症㊁吸烟史等混杂因素后,高水平N L R㊁P L R㊁MH R仍是C A S的独立危险因素,而传统危险因素如老年㊁L D L-C及F P G偏高同样也在本研究中证实㊂这与既往国内外研究结果一致[10-11]㊂在选择素㊁整合素的作用下,中性粒细胞聚集在一起,单核细胞进入病变的动脉中形成泡沫细胞;中性粒细胞还能促使炎症细胞与致动脉粥样硬化性脂蛋白相互作用,加速A S血栓形成;在中性粒细胞活化过程中会释放具有细胞毒性和血栓效应的多形核白细胞胞外诱捕网(N E T s)[12]㊂而淋巴细胞具有对抗A S的作用[13]㊂机体在炎症期间会诱导淋巴细胞在淋巴器官重新分布,外周血淋巴细胞凋亡增强,淋巴细胞进一步减少,这不仅推动了炎症反应的进程,也促进了A S的形成[14]㊂血小板与血管内皮细胞及白细胞的相互作用同时促进了动脉壁炎症的发生㊁发展[15]㊂临床上多数A S患者血小板功能亢进,同时也对各种致敏因素敏感,抗血小板聚集药物也是治疗A S的重要手段㊂N L R综合了固有性(中性粒细胞)和适应性(淋巴细胞)两种不同的炎症反应,反映激活因子与调节因子之间的平衡状态,而P L R结合了血栓形成和炎症参数,它们能更加全面稳定地反映血管的炎症程度㊂MA S S I O T等[16]发现N L R和P L R水平高的患者发生症状性颈内动脉狭窄的比例更高㊂而约90%的颈动脉狭窄性病变是由C A S所致㊂本研究发现N L R的c u t-o f f值为1.98,这与L I等[17]得出的结果相似,他们在中国开展了一项大规模的队列研究,结果发现N L R与C A S的患病率呈正相关,当N L R的临界值为2.06,预测效能最佳㊂石程程等[18]在急性脑梗死患者中发现N L R㊁P L R与C A S斑块的稳定性相关,该研究还纳入了超敏C反应蛋白进行L o g i s t i c回归分析,结果显示只有N L R㊁P L R是C A S 斑块不稳定的独立危险因素,而不是传统炎症指标超敏C反应蛋白㊂这提示N L R㊁P L R这类新型炎症指标可能比传统炎症指标的预测效能更佳㊂单核细胞作为泡沫细胞的前身,参与A S的全过程㊂H D L-C具有抗炎㊁抗氧化应激及促进微血栓溶解的作用,被誉为 血管清道夫 ,是血管的保护性因子㊂MH R整合㊁体现了单核细胞的致炎作用和H D L-C的抗炎作用,对于A S的预测更具优势㊂Y U R T D A S等[19]纳入了300例颈动脉有不同程度狭窄的无症状患者,在血管造影前评估了患者的MH R㊁纤维蛋白原与清蛋白比值(F A R)㊁超敏C反应蛋白,进行相关性分析发现颈动脉狭窄的程度与MH R相关,与F A R㊁超敏C反应蛋白无关㊂以上研究提出MH R诊断颈动脉狭窄的c u t-o f f值为0.61,灵敏度为75%,特异度为70%,均高于本研究[19]㊂这提示MH R可预测C A S的进展,其是否能预测C A S的发生还有待进一步探讨㊂本研究还比较了N L R㊁P L R㊁MH R单独,以及N L R联合P L R预测C A S发生的效能,结果发现, N L R优于P L R,P L R优于MH R,N L R联合P L R与单一N L R比较,差异无统计学意义(P>0.05)㊂当㊃4481㊃检验医学与临床2023年7月第20卷第13期 L a b M e d C l i n,J u l y2023,V o l.20,N o.13Copyright©博看网. All Rights Reserved.N L R的临界值为1.98时,灵敏度为64.77%,特异度为78.30%,其综合预测效能在单一指标中最佳㊂当P L R的c u t-o f f值为105.80时,灵敏度为87.26%,特异度为46.81%,容易误诊㊂N L R联合P L R预测可提高单一N L R的灵敏度,临床中联合应用N L R㊁P L R可减少C A S患者的漏诊㊂B A O等[20]发现在颈动脉血管成形支架置入术患者中N L R预测术后再狭窄的效能强于P L R㊂这也提示N L R可能更适合作为预测C A S的炎症标志物㊂本研究存在一定局限性:分析了N L R㊁P L R㊁MH R与C A S之间的关系,其因果关系还需要进一步研究证实;此外,回顾性研究受到病历资料限制,未能纳入超敏C反应蛋白这类传统炎症指标进行比较,也未能分析性激素水平㊁体质量指数㊁腰围㊁生活方式等其他可能有影响的变量㊂基于以上问题,未来还需要多中心㊁大样本的前瞻性随机对照研究㊂综上所述,高水平的N L R㊁P L R㊁MH R与C A S 的发生密切相关,N L R>1.98㊁P L R>105.8具有较高的预测价值,二者联合预测更为准确,可在临床中推广,这有助于早期筛查出未诊断及亚临床的C A S患者,防止心脑血管不良事件的发生㊂参考文献[1]MA R T I N E Z E,MA R T O R E L L J,R I AM B A U V.R e v i e wo f s e r u m b i o m a r k e r s i n c a r o t i d a t h e r o s c l e r o s i s[J].J V a s c S u r g,2020,71(1):329-341.[2]陶飞,赵旺,琚双五.血小板与淋巴细胞比值㊁中性粒细胞与淋巴细胞比值与急性脑梗死颈动脉粥样硬化斑块的相关性研究[J].临床和实验医学杂志,2021,20(6):606-609.[3]OMA R T,K A R A K A Y A L I M,Y E S I N M,e t a l.M o n o c y t et o h i g h-d e n s i t y l i p o p r o t e i n c h o l e s t e r o l r a t i o i s a s s o c i a t e d w i t h t h e p r e s e n c e o f c a r o t i d a r t e r y d i s e a s e i n a c u t e i s c h e-m i c s t r o k e[J].B i o m a r k M e d,2021,15(7):489-495. [4]H Y U N S,KWO N S,C HO S Y,e t a l.C a n t h e n e u t r o p h i l-t o-l y m p h o c y t e r a t i o a p p r o p r i a t e l y p r e d i c t c a r o t i d a r t e r y s t e n o s i s i n p a t i e n t s w i t h i s c h e m i c s t r o k e:a r e t r o s p e c t i v e s t u d y[J].J S t r o k e C e r e b r o v a s D i s,2015,24(11):2646-2651.[5]R O S S R.A t h e r o s c l e r o s i s:a n i n f l a mm a t o r y d i s e a s e[J].NE n g l J M e d,1999,340(2):115-126.[6]G U C L U K,C E L I K M.P r o g n o s t i c v a l u e o f i n f l a mm a t i o np a r a m e t e r s i n p a t i e n t s w i t h N o n-S T e l e v a t i o n a c u t e c o r o-n a r y s y n d r o m e s[J].A n g i o l o g y,2020,71(9):825-830.[7]L A R MA N N J,HA N D K E J,S C HO L Z A S,e t a l.P r e o p-e r a t i v e n e u t r o p h i l t o l y m p h o c y t e r a t i o a n d p l a t e l e t t o l y m-p h o c y t e r a t i o a r e a s s o c i a t e d w i t h m a j o r a d v e r s e c a r d i o v a s-c u l a r a nd ce r e b r o v a s c u l a r e v e n t s i n c o r o n a r y h e a r t d i s e a s ep a t i e n t s u n d e r g o i n g n o n-c a r d i a c s u r g e r y[J].B M C C a r d i o-v a s r D i s,2020,20(1):1-9.[8]K U N D I H,K I Z I L T U N C E,C E T I N M,e t a l.A s s o c i a t i o n o f m o n o c y t e/H D L-C r a t i o w i t h S Y N T A X s c o r e s i n p a-t i e n t s w i t h s t a b l e c o r o n a r y a r t e r y d i s e a s e[J].H e r z,2016, 41(6):523-529.[9]穆乃外尔㊃萨比尔,阿卜杜外力㊃艾尔肯,美日班㊃外力,等.P L R㊁N L R㊁R DW对急性S T段抬高型心肌梗死患者P C I术后预后的预测价值[J].检验医学与临床,2022, 19(16):2273-2276.[10]韩旭,刘倩,马一涵,等.非糖尿病人群空腹血糖水平对动脉僵硬度进展的影响[J].中华高血压杂志,2021,29(1): 41-47.[11]S O N G P,F A N G Z,WA N G H,e t a l.G l o b a l a n d r e g i o n a lp r e v a l e n c e,b u r d e n,a n d r i s k f a c t o r s f o r c a r o t i d a t h e r o s c l e-r o s i s:a s y s t e m a t i c r e v i e w,m e t a-a n a l y s i s,a n d m o d e l l i n g s t u d y[J].L a n c e t G l o b H e a l t h,2020,8(5):e721-e729.[12]SØR E N S E N O E,B O R R E G A A R D N.N e u t r o p h i l e x t r a-c e l l u l a r t r a p s:t h ed a r k s i de of n e u t r o p h i l s[J].J C l i n I n-v e s t,2016,126(5):1612-1620.[13]A N G K A N A N A R D T,A N O T H A I S I N T A W E E T,M C E-V O Y M,e t a l.N e u t r o p h i l l y m p h o c y t e r a t i o a n d c a r d i o v a s c u-l a r d i s e a s e r i s k:a s y s t e m a t i c r e v i e w a n d m e t a-a n a l y s i s[J].B i o m e d R e s I n t,2018,2018:2703518.[14]B A L T A S,C E L I K T,M I K HA I L I D I S D P,e t a l.T h e r e-l a t i o n b e t w e e n a t h e r o s c l e r o s i s a n d t h e n e u t r o p h i l-l y m p h o-c y t e r a t i o[J].C l i n A p p l T h r o m b H e m o s t,2016,22(5): 405-411.[15]R E A P E T J,G R O O T P H E.C h e m o k i n e s a n d a t h e r o-s c l e r o s i s[J].A t h e r o s c l e r o s i s,1999,147(2):213-225.[16]MA S S I O T N,L A R E Y R E F,V O U R Y-P O N S A,e t a l.H i g h n e u t r o p h i l t o l y m p h o c y t e r a t i o a n d p l a t e l e t t o l y m-p h o c y t e r a t i o a r e a s s o c i a t e d w i t h s y m p t o m a t i c i n t e r n a lc a r o t id a r te r y s t e n o s i s[J].J S t r o k e C e r e b r o v a s c D i s,2019,28(1):76-83.[17]L I B,L A I X,Y A N C,e t a l.T h e a s s o c i a t i o n s b e t w e e n n e u-t r o p h i l-t o-l y m p h o c y t e r a t i o a n d t h e C h i n e s e v i s c e r a l a d i-p o s i t y i n d e x,a n d c a r o t i d a t h e r o s c l e r o s i s a n d a t h e r o s c l e-r o t i c c a r d i o v a s c u l a r d i s e a s e r i s k[J].E x p G e r o n t o l,2020, 139:111019.[18]石程程,张锦,黄小雨,等.血清H c y㊁N L R和P L R水平与急性脑梗死患者颈动脉粥样硬化斑块稳定性及脑梗死复发的关系[J].医学研究杂志,2021,50(3):104-109. [19]Y U R T D AŞM,Y A Y L A L I Y T,ÖZ D E M I R M.T h e r o l eo f m o n o c y t e t o H D L r a t i o i n p r e d i c t i n g c l i n i c a l l y s i g n i f i-c a n t c a r o t i d s t e n o s i s i n p a t i e n t s w i t h a s y m p t o m a t i c c a r o t-i d a r t e r y d i s e a s e[J].R e v A s s o c M e d B r a s,2020,66(8): 1043-1048.[20]B A O X,Z HO U G,X U W,e t a l.N e u t r o p h i l-t o-l y m p h o-c y t e r a t i o a nd p l a te l e t-t o-l y m p h o c y t e r a t i o:n o v e l m a r k e r sf o r t h e d i ag n o s i s a n d p r o g n o s i s i n p a t i e n t s w i th r e s t e n o si s f o l l o w i n g C A S[J].B i o m a r k M e d,2020,14(4):271-282.(收稿日期:2022-10-19修回日期:2023-02-21)㊃5481㊃检验医学与临床2023年7月第20卷第13期 L a b M e d C l i n,J u l y2023,V o l.20,N o.13Copyright©博看网. All Rights Reserved.。

Velocityfield statistics in homogeneous steady turbulence obtained using a high-resolution direct numerical simulationToshiyuki Gotoh a)Department of Systems Engineering,Nagoya Institute of Technology,Showa-ku,Nagoya466-8555,JapanDaigen FukayamaInformation and Mathematical Science Laboratory,Inc.,2-43-1,Ikebukuro,Toshima-ku,Tokyo171-0014,JapanTohru NakanoDepartment of Physics,Chuo University,Kasuga,Bunkyo-ku,Tokyo112-8551,JapanVelocityfield statistics in the inertial to dissipation range of three-dimensional homogeneous steadyturbulentflow are studied using a high-resolution DNS with up to Nϭ10243grid points.The rangeof the Taylor microscale Reynolds number is between38and460.Isotropy at the small scales ofmotion is well satisfied from half the integral scale͑L͒down to the Kolmogorov scale͑␩͒.TheKolmogorov constant is1.64Ϯ0.04,which is close to experimentally determined values.The thirdorder moment of the longitudinal velocity difference scales as the separation distance r,and itscoefficient is close to4/5.A clear inertial range is observed for moments of the velocity differenceup to the tenth order,between2␭Ϸ100␩and L/2Ϸ300␩,where␭is the Taylor microscale.Thescaling exponents are measured directly from the structure functions;the transverse scalingexponents are smaller than the longitudinal exponents when the order is greater than four.Thecrossover length of the longitudinal velocity structure function increases with the order andapproaches2␭,while that of the transverse function remains approximately constant at␭.Thecrossover length and importance of the Taylor microscale are discussed.©2002AmericanInstitute of Physics.͓DOI:10.1063/1.1448296͔I.INTRODUCTIONKolmogorov studied the statistical laws of a velocity field for small scales of turbulent motion at high Reynolds numbers.1,2Two hypotheses were introduced in his theory ͑hereafter K41for short͒:local isotropy and homogeneity exists;and there is an inertial range in the energy spectrum of theflow that is independent of viscosity and large-scale properties at sufficiently high Reynolds numbers.The most prominent conclusion of his theory is the presence of the Kolmogorov spectrum E(k)ϭK⑀¯2/3kϪ5/3in the inertial range,where⑀¯is the average rate of energy dissipation per unit mass and K is a universal constant.Since K41,there has been a considerable amount of ef-fort made to study the turbulent velocityfield statistics in the inertial range,and the energy spectrum has been a central quantity of interest.The Kolmogorov spectrum and constant have been measured infield and laboratory experiments.3–7 The exponent for the inertial range spectrum is now widely accepted asϪ5/3,with a small correction to account forflow intermittency.The Kolmogorov constant K is between1.5 and 2.After studying the results of many experiments, Sreenivasan stated that K is1.62Ϯ0.17.7The spectral theory of turbulence has also been used to predict the Kolmogorov constant.The value of K is1.77when the Lagrangian history direct interaction approximation͑LHDIA͒is used,8,9and 1.72when the Lagrangian renormalized approximation ͑LRA͒is used.10,11These are fully systematic theories that do not contain any ad hoc parameters.Direct numerical simulations͑DNSs͒of turbulentflows are now performed at higher Reynolds numbers,due to the recent dramatic increase in computational power.In the early 90’s,the resolution of DNS reached Nϭ5123grid points with a Taylor microscale Reynolds number R␭of 210ϳ240.12–20Most high-resolution DNSs have been per-formed for steady turbulence conditions to achieve high Rey-nolds numbers and obtain reliable statistics.Although results were reported with R␭greater than200,an inertial range spectrum was observed only for the lowest narrow wave number band at which forcing was applied.The Kolmogorov constant was inferred to be about1.5ϳ2in Ref.14and1.62 in Ref.16,but these results are not convincing,due to the insufficient width of the scaling range,anisotropy of theflow field,limited ensemble size,forcing techniques used,and numerical limitations of the simulations.Intermittency has also attracted the interest of research-ers.Since Kolmogorov’s intermittency theory͑hereafter K62͒,21many theoretical and statistical models of intermit-tency have been developed.4,22,23The scaling exponents of higher order structure functions for velocity differences in the inertial range were studied intensively.Intermittency in-creases with a decrease in the size of the scales of motion. The small-scale statistics gradually deviate from a Gaussian distribution,and the scaling exponents differ from those pre-dicted by K41.Experiments at very high Reynolds numbers have beena͒Electronic mail:gotoh@system.nitech.ac.jpPHYSICS OF FLUIDS VOLUME14,NUMBER3MARCH200210651070-6631/2002/14(3)/1065/17/$19.00©2002American Institute of Physicsperformed in the atmospheric boundary layer and in huge wind tunnels,and the measured scaling exponents were found to deviate from K41scaling.5,6,24,25,84However,there have been arguments made about the lack of small-scaleflow isotropy and homogeneity in these experiments,which might be affected by the large-scale shear.25,26For experiments at moderate Reynolds numbers under relatively well-controlled laboratory conditions,the width of the scaling range is usually not large enough to determine the scaling exponents precisely.Extended self-similarity͑ESS͒has been exploited to overcome this difficulty and applied to various turbulentflows in both experiments and DNSs.28–31 The idea is to measure the scaling exponents of the structure functions when they are plotted against the third order lon-gitudinal structure function,rather than to use the separation distance.The width of the scaling range is longer than that obtained with the usual method at low to moderate Reynolds numbers.The scaling exponents are anomalous,but do agree with those obtained from high Reynolds number experiments up to a certain order.24,28–31However,there is no consensus as to why the structure functions give a longer inertial range, or what is missing from theflow statistics as a result.Also, there is no unique way to determine the scaling exponents for the transverse and mixed velocity structure functions,be-cause those higher order structure functions can be plotted against other types of third order structure functions as well as the third order longitudinal structure function.There also have been arguments about whether the scal-ing exponents for the longitudinal and transverse structure functions at small scales are equal.25–27,32–38Many experi-ments and DNSs have reported that higher order longitudinal scaling exponents are larger than transverse ones.However, some researchers have argued that the difference is due to deviation from the assumed conditions,such as local homo-geneity,isotropy,and the independence of small scales from macroscale parameters.They have suggested that when the Reynolds number becomes large enough,the difference will vanish.36,37,39,40In many aspects of turbulence research,there have been questions posed about the extent to which the local homoge-neity and isotropy of the turbulent velocityfield are attained. This will affect the small-scale statistics significantly.Recent experimental studies have shown that local isotropy is par-tially satisfied for lower order moments.25,26,37However,it is not sufficient to examine only the conditions assumed in the above studies,and only a limited knowledge of the trueflow conditions is available so far.26,37,38A DNS with a sufficiently large grid size provides abetter opportunity to examine the points raised above.It hasthe advantage that any physical quantity can be measureddirectly without deforming theflowfield.In the presentstudy,a series of large scale DNSs have been performed at ahigh resolution of up to Nϭ10243and R␭ϭ460.41–45The inertial range of the turbulencefield has a considerablelength,and useful velocity statistics can be extracted such asthe Kolmogorov constant,the energy spectrum,velocitystructure functions up to the tenth order,their scaling expo-nents,and probability density functions for velocity differ-ences.To the authors’best knowledge,these are thefirstDNS data in the inertial range;the data provide new insightinto the inertial and dissipation ranges.The main purposes of the present paper are to describethe statistics of the velocityfield in an incompressible steadyturbulentflow obtained from the DNS,and to reexaminecurrent knowledge of turbulence,developed since K41.Thepaper is organized as follows.The numerical aspects of thepresent DNS are described in Sec.II,and the energy spec-trum is examined in Sec.III.The variation of single pointquantities and probability density functions͑PDFs͒with theReynolds number is discussed in Sec.IV.The isotropy of thesecond and third order moments of the velocity difference isexamined in Sec.V,and the energy budget is examined interms of the Ka´rma´n–Howarth–Kolmogorov equation inSec.VI.The structure functions and scaling exponents arediscussed in Sec.VII.Section VIII presents an analysis ofthe crossover lengths of the structure functions.Finally,asummary and conclusions are provided in Sec.IX.II.NUMERICAL SIMULATIONThe Navier–Stokes equations are integrated in Fourierspace for unit density:ͩץץtϩ␯k2ͪuϭP͑k͒•F͓uÃ␻͔kϩf,͑1͒͗f͑k,t͒f͑Ϫk,s͒͘ϭP͑k͒F͑k͒4␲k2␦͑tϪs͒,͑2͒where␻is the vorticity vector,P͑k͒is the projection opera-tor,F denotes a Fourier transform,and f is a solenoidal Gaussian random force that is white in time.The spectrum of the random force F(k)is constant over the low wave number band and zero otherwise;the force is normalized asTABLE I.DNS parameters and statistical quantities of the runs.T eddya v is the period used for the time average.R␭N k max␯c f Forcing range T eddya v E⑀¯L␭␩(ϫ10Ϫ2)K 38128360 1.50ϫ10Ϫ2 1.30ͱ3рkрͱ1222.6 1.99 1.190.8910.501 4.10¯5425631217.00ϫ10Ϫ30.70ͱ3рkрͱ1214.9 1.390.6270.8290.393 2.72¯702563121 4.00ϫ10Ϫ30.50ͱ3рkрͱ1249.7 1.160.4570.7850.318 1.93¯1255123241 1.35ϫ10Ϫ30.50ͱ3рkрͱ12 5.52 1.250.4920.7440.1850.841¯2845123241 6.00ϫ10Ϫ40.501рkрͱ6 3.03 1.960.530 1.2460.1490.449 1.64 38110243483 2.80ϫ10Ϫ40.511рkрͱ6 4.21 1.740.499 1.1390.09890.258 1.63 46010243483 2.00ϫ10Ϫ40.511рkрͱ6 2.14 1.790.506 1.1500.08410.199 1.64 1066Phys.Fluids,Vol.14,No.3,March2002Gotoh,Fukayama,and Nakano͵ϱF ͑k ͒dk ϭ⑀¯in ,͑3͒where ⑀¯in is the average rate of the energy input per unit mass.A pseudo-spectral code was used to compute the con-volution sums,and the aliasing error was effectively re-moved.The time integration was performed using the fourth order Runge–Kutta–Gill method.Physical quantities of turbulent flow include the total energyE ͑t ͒ϭ12͗u 2͘ϭ32u ¯2ϭ͵ϱE ͑k ͒dk ,͑4͒the average energy dissipation per unit mass⑀¯ϭ2␯͵ϱk 2E ͑k ͒dk ,͑5͒the integral scaleL ϭͩ3␲4͵ϱk Ϫ1E ͑k ͒dkͪͲE ,͑6͒the Taylor microscale␭ϭͩ5EͲ͵ϱk 2E ͑k ͒dkͪ1/2,͑7͒the Taylor microscale Reynolds numberR ␭ϭu ¯␭␯,͑8͒and the Kolmogorov scale␩ϭͩ␯3⑀¯ͪ1/4.͑9͒The range of the Taylor microscale Reynolds number was 38to 460.The characteristic parameters of the DNS are listed in Table I.43Most of these are identical to Gotoh and Fukayama,43but the averaging time for R ␭ϭ381was ex-tended to 4.21large eddy turnover times.A statistically steady state was confirmed by observing the time evolutionof the total energy,the total enstrophy,and the skewness of the longitudinal velocity derivative.The statistical averages were computed as time averages over tens of large eddy turnover times for the lower Reynolds number flows,and over a few large eddy turnover times for the higher Reynolds number flows.The resolution condition k max ␩Ͼ1was satis-fied for most runs,except for R ␭ϭ460in which k max ␩was slightly less than unity (k max ␩ϭ0.96).This does not ad-versely affect the results in the inertial range.The computational time required for runs at a N ϭ10243resolution varied,depending on the statistical data that was gathered.Typically,60h was required for one large eddy turnover time.The total time of the computations was more than 500h for the longest run (R ␭ϭ381).Data col-lected during the transition period to steady state ͑about six large eddy turnover times ͒were discarded.The relatively long time required to attain steady state was due to the low wave number band forcing.This imposes a severe computa-tional putations with R ␭р284were per-formed on a Fujitsu VPP700E parallel vector machine with 16processors at RIKEN.Simulations of higher R ␭were per-formed on a Fujitsu VPP5000/56with 32processors at the Nagoya University Computation Center.III.ENERGY SPECTRUMFigure 1shows the three-dimensional energy spectrum calculated for each run.All of the curves are scaled to the Kolmogorov units and multiplied by k 5/3.As the Reynolds number increases,the curves extend toward lower wave numbers.The curves of flows with Reynolds numbers larger than R ␭ϭ284contain a finite plateau,which indicates that E (k )ϰk Ϫ5/3.There is a bump when 0.04рk ␩р0.3at the high end of the inertial range,which is consistent with pre-vious experimental and numerical observations.6,16The nor-malized energy transfer flux,defined by1⑀¯⌸͑k ͒ϭ1⑀¯͵kϱT ͑k Ј͒dk Ј͑10͒is shown in Fig.2,where T (k )is a nonlinear energy transfer function in the energy spectrum equation.4,22Between0.007рk ␩р0.04,⌸(k )/⑀¯is approximately constantand FIG.1.Scaled energy spectra,⑀¯Ϫ1/4␯Ϫ5/4(k ␩)5/3E (k ).The inertial range is 0.007рk ␩р0.04and K ϭ1.64Ϯ0.04.A horizontal line indicates K ϭ1.64.FIG.2.Normalized energy transfer flux,⌸(k )/⑀¯for R ␭ϭ381and 460.1067Phys.Fluids,Vol.14,No.3,March 2002Velocity field statistics in homogeneousclose to unity;thus the flow is in an equilibrium state over the inertial range of the energy spectrum,corresponding to the plateaus in Fig.1.The Kolmogorov constant given in Table I is determined using a least square fit between 0.007рk ␩р0.04on the R ␭Ͼ284curves.In Ref.43,the Kolmog-orov constant was reported as K ϭ1.65Ϯ0.05.However,the averaging time has since been extended for the R ␭ϭ381run.The R ␭ϭ478run differs slightly from statisticalequilibrium,since ⌸(k )/⑀¯is not exactly one;for this reason,the R ␭ϭ478data were not used for this analysis.The Kol-mogorov constant,computed using the data only from the R ␭ϭ381and 460runs,isK ϭ1.64Ϯ0.04,͑11͒which is in good agreement with experimental values and recent DNS data.7,16There are many DNSs reporting the Kolmogorov constant higher than the value 1.64.However,the length of the inertial range in those DNSs is not long enough to clearly observe the k Ϫ5/3range,and the top of the bump of the compensated energy spectrum k 5/3E (k )is un-derstood as the inertial range,so that the Kolmogorov con-stant is read as about 2as seen in Fig.1.16The Kolmogorov constant 1.64is also close to the value obtained using the LHDIA ͑1.77͒,8,9the LRA ͑1.72͒.10,11These spectral theories of turbulence are consistent with Lagrangian dynamics,arederived systematically,and contain no ad hoc parameters.Figure 3shows the one-dimensional energy spectrum ob-tained from the present DNS with R ␭ϭ460,from experi-ments,and from the LRA.The agreement between the curves is satisfactory.Therefore we conclude that the present DNS has successfully calculated a homogeneous turbulent flow field in the inertial range of the energy spectrum.IV.ONE-POINT STATISTICS A.MomentsSome one-point moments of the velocity field areS 3͑u ͒ϵ͗u 3͗͘u 2͘3/2,S 3͑u x ͒ϵ͗u x 3͗͘x 2͘3/2,͑12͒K 4͑u ͒ϵ͗u 4͗͘u 2͘2,K 4͑u x ͒ϵ͗u x 4͗͘u x 2͘2,K 4͑u y ͒ϵ͗u y 4͗͘u y 2͘2,͑13͒where u is the velocity component in the x direction.The variation of these moments with the Reynolds number is shown in Fig.4and listed in Table II.The general behavior of the curves is consistent with previous DNS and experi-mental data.13,14,18,19,26,46,47There are small effects of rela-tively low resolution on S 3and K 4for the velocity deriva-tives for R ␭ϭ381and 460data.The skewness factor of the velocity u is very small for runs with the R ␭р125,and isofparison of one-dimensional energy spectra.Symbols:experi-ments,solid line:present DNS (R ␭ϭ460),dashed line:statistical theory ͑LRA and MLRA ͒.FIG.4.Variation of the moments of the velocity and velocity gradient withthe Reynolds number.Line:present DNS,circle:K 4(u y )͑Jime´nez et al.,Ref.13͒,solid square:K 4(u )͑Jime ´nez et al.,Ref.13͒,square:K 4(u x )͑Wang et al.,Ref.14͒,plus:K 4(u x )͑Vedula and Yeung,Ref.18͒,star:ϪS 3(u x )͑Wang et al.,Ref.14͒.TABLE II.Moments of the velocity and velocity derivatives.R ␭S 3(u )K 4(u )S 3(ץu /ץx )K 4(ץu /ץx )K 4(ץu /ץy )380.0227 2.89Ϫ0.520 4.14 5.16540.00563 2.86Ϫ0.517 4.47 6.00700.00473 2.93Ϫ0.519 4.81 6.621250.0820 2.94Ϫ0.529 5.658.192840.0231 2.77Ϫ0.531 6.6310.1381Ϫ0.246 2.98Ϫ0.5747.9012.2460Ϫ0.1682.89Ϫ0.5457.9111.71068Phys.Fluids,Vol.14,No.3,March 2002Gotoh,Fukayama,and Nakanothe order of 0.2for runs with the R ␭у284.The relatively large values of the velocity skewness are caused by the shorter averaging time used compared to the low Reynolds number runs.Since most of the energy resides in the lowest wave number band,there are persistent large fluctuations of the large scales of motion over longer time period.The longer time average or the forcing at larger wave numbers would yield smaller velocity skewness.The flatness factor of the velocity field is close to three,which is the Gaussian value.The skewness factor of the longitudinal velocity deriva-tives is very insensitive to the Reynolds number,S 3͑u x ͒ϰR ␭0.0370,͑14͒where the exponent is determined by a least square fit.Theaverage value is Ϫ0.53,which is consistent with experimen-tal observations over the range of Reynolds numbers studied in the present work.However,the exponent is smaller than indicated by the experimental data.26,46The flatness factors for the longitudinal and transverse velocity derivatives in-crease with the Reynolds number asK 4͑u x ͒ϰR ␭0.266,K 4͑u y ͒ϰR ␭0.335.͑15͒The exponent of K 4(u y )is larger than that of K 4(u x );thus,the PDF for the transverse velocity derivative has longer tails than those of the longitudinal velocity derivative.From ex-perimental observations,Shen and Warhaft reported thatK 4(u x )ϰR ␭0.37and K 4(u y )ϰR ␭0.25.26Since there is scatter in the experimetal data,the exponents in Eq.͑15͒by the present DNS are not inconsistent with the experimental data.Van Atta and Antonia studied the Reynolds number dependence of S 3(u x )and K 4(u x ),46and found thatS 3͑u x ͒ϰR ␭0.12,K 4͑u x ͒ϰR ␭0.32for ␮ϭ0.2,͑16͒S 3͑u x ͒ϰR ␭0.15,K 4͑u x ͒ϰR ␭0.41for ␮ϭ0.25,͑17͒where ␮is the exponent defined by ͗⑀r 2͘ϰr Ϫ␮for the locally averaged energy dissipation rate.4,21Generally,the Reynolds number dependency of S 3and K 4in our DNSs is weaker than observed in the experiments,irrespective of the type of forcing used.We believe this is because the range of Rey-nolds numbers in DNS is smaller than experimental flows,and there remain small-scale anisotropy effects in the experi-ments.B.Probability density functionsThe probability density function conveys information about single-point velocity statistics.It has been one of the central issues of turbulence research in the last decade.Single-point PDFs for the velocity and its derivatives are shown in Figs.5–7.A longer time period was necessary for the time average to obtain well-converged PDF for the ve-locity Q (u ).The distribution Q (u )is close to Gaussian,and its tail extends to very low values of the order of 10Ϫ10.Such values have not been reported in the literature.The Q (u )curve for R ␭ϭ381is skewed negatively,but this is attributed to the insufficient time-averaging period ͑four large eddy turnover times ͒that was used.The overall trend is that Q (u )decays faster than a Gaussian distribution at large ampli-tudes.This behavior was also observed in one-dimensional decaying and forced Burgers turbulence.48,49Jime´nez has shown that the PDF Q (u )is slightly sub-Gaussian as the energy spectrum decays faster than k Ϫ1.50FIG.5.Variation of velocity PDF with the Reynoldsnumber.FIG.6.Variation of the longitudinal velocity derivative PDF with the Rey-noldsnumber.FIG.7.Variation of the transverse velocity derivative PDF with the Rey-nolds number.1069Phys.Fluids,Vol.14,No.3,March 2002Velocity field statistics in homogeneousThis is consistent with the present DNS results.Studies of the Q (u )tail predict that Q (w )ϰexp(Ϫc ͉w ͉3)when the forc-ing has a short correlation time.51,52Here,w ϭu /͗u 2͘1/2is the normalized velocity amplitude and c is a nondimensional constant.The asymptotic form of Q (u )was examined by plotting ln ͓Ϫln(Q (w )͔against ln ͉w ͉;however,the Q (w )tails were too short to determine the true asymptotic form.The PDF for the longitudinal velocity derivative is slightly skewed,as expected from the finite negative value of the skewness factor.The tail becomes longer as the Reynolds number increases.Figure 7shows that the PDF of the trans-verse derivative is symmetric and has a longer tail than the longitudinal derivative.There are many theories for the PDF of the velocity derivative.The asymptotic tail of Q (ץu /ץy )is presented in Fig.8,in which both the positive and negative sides are plotted by assuming that the PDF is symmetric.The tails gradually become longer as the Reynolds number increases;therefore,Q (s )is Reynolds-number dependent,and cannot be represented in a single stretched exponential form as Q (s )ϰexp(Ϫb ͉s ͉h ),where s is the normalized amplitude of ץu /ץy and b is a nondimensional constant that is a function of the Reynolds number.53V.ISOTROPYThe hypothesis of isotropy of the flow field is one of the key components of K41.There are various methods to ex-amine the degree of isotropy.One measure of isotropy can be obtained from the relations between the second and third order longitudinal and transverse velocity structure func-tions.These areD LL ϵ͗͑␦u r ͒2͘,D TT ϵ͗͑␦v r ͒2͘,͑18͒D LLL ϵ͗͑␦u r ͒3͘,D LTT ϵ͗␦u r ͑␦v r ͒2͘,͑19͒where␦u r ϵ͑u ͑x ϩr ͒Ϫu ͑x ͒͒•r /r ,͑20͒␦v r ϵ͑u ͑x ϩr ͒Ϫu ͑x ͒͒•͑I Ϫrr /r 2͒•e Ќ,͑21͒and e Ќis the unit vector perpendiculer to r ,and I is the unit tensor.Then the isotropy and incompressibility relations areD TT ͑r ͒ϭD LL ͑r ͒ϩr 2dD LL ͑r ͒dr ,͑22͒D LTT ͑r ͒ϭ16ddrrD LLL ͑r ͒.͑23͒In DNS,the solenoidal property of the Fourier amplitude velocity vector u ͑k ͒is always satisfied to the level of nu-merical error,which is smaller than 10Ϫ15.Thus,the accu-racy of the above relations depends solely on the deviation from isotropy.The two sides of Eqs.͑22͒and ͑23͒are com-pared for R ␭ϭ125,381,and 460in Figs.9and 10.The curves in the figures are divided by r 2/3and r ,respectively,and the vertical axes of the plots are linear.The thick lines represent the left hand sides of Eqs.͑22͒and ͑23͒,and the thin lines correspond to the right-hand sides.The isotropy of the second and third order moments is excellent for scales less than L /2.The difference at larger separations is caused by the anisotropy due to the small number of energy-containing Fourier modes.The curves for R ␭ϭ381and460FIG.8.Variation of the asymptotic tail of the transverse velocity derivative PDF with the Reynolds number.Both positive and negative sides are plot-ted.The rightmost curve corresponds to R ␭ϭ460.FIG.9.Isotropy relation at the second order.Thin line:D TT (r )r Ϫ2/3,thick line:(D LL (r )ϩ(r /2)(dD LL (r )/dr ))r Ϫ2/3.L /␩and ␭/␩are shown for R ␭ϭ460.FIG.10.Isotropy relation at the third order.Thin line:D LTT (r )r Ϫ1,thick line:((1/6)(d /dr )rD LLL (r ))r Ϫ1.L /␩and ␭/␩are shown for R ␭ϭ460.1070Phys.Fluids,Vol.14,No.3,March 2002Gotoh,Fukayama,and Nakanoin Fig.9are not horizontal,suggesting that the second order structure function does not scale as r 2/3.The scaling expo-nents will be examined later in this paper.The isotropic re-lations,such as D 1122ϭD 1133and D 2222ϭ3D 2233ϭD 3333,and Hill’s higher order relations were not computed.54VI.KA´RMA ´N–HOWARTH–KOLMOGOROV EQUATION The energy budget for various scales is described by the Ka´rma ´n–Howarth–Kolmogorov ͑KHK ͒equation,45⑀¯r ϭϪD LLL ϩ6␯ץD LL ץrϩZ ͑24͒for steady turbulence,4,55,56where Z (r )denotes contributions due to the external force given by Z ͑r ,t ͒ϭ͵Ϫϱt͗␦f ͑r ,t ͒•␦f ͑r ,s ͒͘dsϭ12r͵0ϱͩ115ϩsin kr ͑kr ͒3ϩ3cos kr ͑kr ͒4Ϫ3sin kr ͑kr ͒5ͪF ͑k ͒dk .͑25͒Since the external force spectrum F (k )is localized in arange of low wave numbers,the asymptotic form of Z (r )for small separations is given asZ ͑r ͒ϭ235⑀¯in k f 2r 3,k f 2ϵ͐0ϱk 2F ͑k ͒dk͐0ϱF ͑k ͒dk.͑26͒A generalized Ka´rma ´n–Howarth–Kolmogorov equation has also been derived:57–6343⑀¯r ϭϪ͑D LLL ϩ2D LTT ͒ϩ2␯ץץr͑D LL ϩ2D TT ͒ϩW ,͑27͒where W ͑r ͒ϭ4r͵0ϱͩ13ϩcos kr ͑kr ͒2Ϫsin kr͑kr ͒3ͪF ͑k ͒dk ,Ϸ215⑀¯in r 3k f 2for ͉k f r ͉Ӷ1.͑28͒Equation ͑24͒is recovered by substituting Eqs.͑22͒and ͑23͒into Eq.͑27͒.Figure 11shows the results obtained when each term of Eq.͑24͒is divided by ⑀¯r for R ␭ϭ460.Curves in which r /␩is larger than r /␩ϭ1200are not shown,because the sign of D LLL changes.A thin horizontal line indicates the Kolmog-orov value 4/5.When the separation distance decreases,the effect of the large scale forcing used in the present DNS decreases quickly,while the viscous term grows gradually.The third order longitudinal structure function D LLL quickly rises to the Kolmogorov value,remains there over the iner-tial range ͑between r /␩Ϸ50and 300͒,and then decreases.In the inertial range,the force term decreases as r 3according to Eq.͑26͒,while the viscous term increases as r ␨2Ϫ1(␨2Ͻ1)when r decreases.͓Since each term in the figure is divided by (⑀¯r ),the slope of each curve is 2and ␨2Ϫ2,respectively.͔The sum of the three terms in the right hand side of Eq.͑24͒divided by ⑀¯r is close to 4/5,the Kolmogorov value.The deviation of the sum from the 4/5law at the smallest scales is due to the slightly lower resolution of the data at these scales ͑k max ␩is close to one ͒.At larger scales greater than r /␩ϭ700,the deviation is caused by the finiteness oftheFIG.11.Terms in the Ka´rma ´n–Howarth–Kolmogorov equation when R ␭ϭ460.Thin solid line:4/5.FIG.12.Kolmogorov’s 4/5law.L /␩and ␭/␩are shown for R ␭ϭ460.The maximum values of the curves are 0.665,0.771,0.781,and 0.757for R ␭ϭ125,284,381,and 460,respectively.FIG.13.Terms in the generalized Ka´rma ´n–Howarth–Kolmogorov equation for R ␭ϭ460.Thin solid line:4/3.1071Phys.Fluids,Vol.14,No.3,March 2002Velocity field statistics in homogeneousensemble,which indicates the persistent anisotropy of the larger scales.The above findings are consistent with the cur-rent knowledge of turbulence developed since Kolmogorov,although confirmation of some aspects of turbulence using actual data is new from both a numerical and experimental point of view.56,59–65It is interesting and important to observe when the Kol-mogorov 4/5law is satisfied as the Reynolds numberincreases.6,66–69Figure 12shows curves of ϪD LLL (r )/(⑀¯r )for various Reynolds numbers.In this figure,the 4/5law applies when the curves are horizontal.The portion of the curves in which r /␩Ͼ1200is not shown.Although there is a small but finite horizontal range when R ␭Ͼ284,the level of the plateau is still less than the Kolmogorov value.The maximum values of the curves are 0.665,0.771,0.781,and 0.757for R ␭ϭ125,284,381,and 460,respectively.The value 0.781for R ␭ϭ381is 2.5%less than 0.8.An asymptotic state is approached slowly,which is consistent with recent studies.However,the asymptote is approached faster than predicted by the theoretical estimate.66,69Theslow approach is due to the fact that D LLL (r )is the third order structure function and most positive contributions are canceled by negative ones.Thus only the slight asymmetry of the ␦u r PDF contributes to D LLL .The level of the plateau of the R ␭ϭ460curve is slightly less than the others.A higher value would be expected if the time average period used for the R ␭ϭ460run were longer.The generalized Ka´rma ´n–Howarth–Kolmogorov equa-tion Eq.͑27͒is also examined in a similar fashion.Figure 13shows each term of the equation divided by ⑀¯r ;a horizontal line indicates the 4/3law.The agreement between the present data and theory is satisfactory.The third order moment slowly approaches the Kolmogorov value 4/3,as shown in Fig.14.The maximum values of the curves of the 4/3law are 0.564,1.313,1.297,and 1.259for R ␭ϭ125,284,381,and 460,respectively.VII.STRUCTURE FUNCTIONS AND SCALING EXPONENTSThe velocity structure functions are defined asS p L ͑r ͒ϭ͉͗␦u r ͉p͘,S p T ͑r ͒ϭ͉͗␦v r ͉p͘,FIG.14.Kolmogorov’s 4/3law.L /␩and ␭/␩are shown for R ␭ϭ460.The maximum values of the curves for the 4/3law are 0.564,1.313,1.297,and 1.259for R ␭ϭ125,284,381,and 460,respectively.FIG.15.Variation of the ␦u r PDF with r for R ␭ϭ381.From the outermostcurve,r n /␩ϭ2n Ϫ1dx /␩ϭ2.38ϫ2n Ϫ1,n ϭ1,...,10,where dx ϭ2␲/1024.The inertial range corresponds to n ϭ6,7,8.Dotted line:Gaussian.FIG.16.Variation of PDF for ␦v r with r at R ␭ϭ381.The classification of curves is the same as in Fig.17.FIG.17.Convergence of the tenth order accumulated moments C 10(␦u r )at R ␭ϭ381for various separations r n /␩ϭ2.38ϫ2n Ϫ1,n ϭ1,...,10.Curves are for n ϭ1,...10from the uppermost,and the inertial range corresponds to n ϭ6,7,8.1072Phys.Fluids,Vol.14,No.3,March 2002Gotoh,Fukayama,and Nakano。

Journal of Logic,Language and Information(2005)14:133–148C Springer2005 Kolmogorov Complexity for Possibly Infinite ComputationsVER´ONICA BECHER and SANTIAGO FIGUEIRADepartamento de Computaci´o n,Facultad de Ciencias Exactas y Naturales,Universidad de Buenos Aires,ArgentinaE-mail:vbecher@dc.uba.ar,sfigueir@dc.uba.ar(Received5August2003;infinal form8June2004)Abstract.In this paper we study the Kolmogorov complexity for non-effective computations,that is, either halting or non-halting computations on Turing machines.This complexity function is defined as the length of the shortest input that produce a desired output via a possibly non-halting computation. Clearly this function gives a lower bound of the classical Kolmogorov complexity.In particular,if the machine is allowed to overwrite its output,this complexity coincides with the classical Kolmogorov complexity for halting computations relative to thefirst jump of the halting problem.However,on machines that cannot erase their output–called monotone machines–,we prove that our complexity for non effective computations and the classical Kolmogorov complexity separate as much as we want. We also consider the prefix-free complexity for possibly infinite computations.We study several properties of the graph of these complexity functions and specially their oscillations with respect to the complexities for effective computations.Key words:infinite computations,Kolmogorov complexity,monotone machines,non-effective computations,program-size complexity,Turing machines1.IntroductionThe Kolmogorov or program-size complexity(Kolmogorov,1965)classifies strings with respect to a static measure for the difficulty of computing them:the length of the shortest program that computes the string.A low complexity string has a short algorithmic description from which one can reconstruct the string and write it down.Conversely,a string has maximal complexity if it has no algorithmic description shorter than its full length.Due to an easy but consequential theorem of invariance,program-size complexity is independent of the universal Turing machine (or programming language)being considered,up to an additive constant.Thus, program-size complexity counts as an absolute measure of complexity(see(Li and Vit´a nyi,1997)for a thorough exposition of the subject).The prefix-free version of program-size complexity,independently introduced by Chaitin(Chaitin,1975)and Levin(Levin,1974),also serves as a measure of quantity of information,being formally identical to Shanon’s information theory (Chaitin,1975).134V.BECHER AND S.FIGUEIRA In this paper we study the Kolmogorov complexity for non-effective com-putations,that is,either halting or non-halting computations on Turing ma-chines.This complexity function,notated with K∞,is defined as the length of the shortest inputs that produce a desired output via a possibly non-halting computation.The ideas behind K∞(more precisely its prefix-free variant H∞) have been treated by Chaitin(1976a)and Solovay in(1977),and later in (Becher et al.,2001).In a recent paper(Ferbus-Zanda and Grigorieff,2004) Grigorieff and Ferbus-Zanda give a machine-free mathematical formalization of K∞.They show that K∞coincides with the Kolmogorov complexity of MAX Rec, the class of functions obtained as the maximum of a sequence of total recursive functions{0,1}∗→N.Clearly this function K∞gives a lower bound of the classical Kolmogorov com-plexity.In particular,if the machine is allowed to overwrite its output,K∞coincides with the classical Kolmogorov complexity for halting computations relative to the first jump of the halting problem.However,on machines that cannot erase their out-put–called monotone machines–,we prove that K∞and the classical Kolmogorov complexity separate as much as we want.We also consider the prefix-free complexity for possibly infinite computations, notated H∞.This complexity function was defined in(Becher et al.,2001)without a detailed study of its properties.We study several properties of the graph of K∞and H∞,specially their oscil-lations with respect to the respective complexities for effective computations.We also consider the behaviour of the complexity function along the prefix ordering on {0,1}∗in the same vein as in(Katseff and Sipser,1981).2.DefinitionsN is the set of natural numbers,and we work with the binary alphabet{0,1}.As usual,a string is afinite sequence of elements of{0,1},λis the empty string and {0,1}∗is the set of all strings.{0,1}ωis the set of all infinite sequences of{0,1}, i.e.,the Cantor space.{0,1}≤ω{0,1}∗∪{0,1}ωis the set of allfinite or infinite sequences of{0,1}.For any n∈N,{0,1}n is the set of all strings of length n.For a∈{0,1}∗,|a|denotes the length of a.If a∈{0,1}∗and A∈{0,1}ωwe denote with a n the prefix of a of length min(n,|a|)and with A n the prefix of the infinite sequence A of length n.For a,b∈{0,1}∗,we write a b if a is a prefix of b.In this case,we also say that b is an extension of a.A set X⊆{0,1}∗is prefix-free if no a∈X has a proper prefix in X.X⊆{0,1}∗is closed under extensions when for every a∈X,all its extensions are also in X.We assume the recursive bijection str:N→{0,1}∗such that str(i)is the i-th string in the length-lexicographic order over{0,1}∗.We also assume the one to one recursive function·:{0,1}∗→{0,1}∗which for every string s=b1b2...b n−1b n, s=0b10b2...0b n−11b n.This function will be useful to code inputs to Turing machines which require more than one argument.KOLMOGOROV COMPLEXITY FOR POSSIBLY INFINITE COMPUTATIONS135 If f is any partial function then,as usual,we write f(p)↓when it is defined, and f(p)↑otherwise.2.1.P OSSIBLY I NFINITE C OMPUTATIONS ON M ONOTONE M ACHINESWe work with Turing machines with a one-way read-only input tape,some work tapes,and an output tape.The input tape contains afirst dummy cell(representing the empty input)followed by0’s and1’s representing the input,and then a special end-marker indicating the end of the input.Notice that the end-marker allows the machine to know exactly where the input ends.We shall refer to two architectures of Turing machines,regarding the input and output tapes.A monotone Turing machine has a one-way write-only output tape.A prefix machine is a Turing machine with a one-way input tape containing no blanks (just zeroes and ones).Since there is no external delimitation of the input tape, the machine may eventually read the entire input tape.A prefix monotone machine contains no blank end-marker in the input tape and it has a one-way write-only output tape.A computation on a machine starts with the input head scanning the leftmost dummy cell.The output tape is written one symbol at a time.In a(prefix)monotone machine,the output grows monotonically with respect to the prefix ordering in {0,1}∗as the computational time increases.A possibly infinite computation is either a halting or a non halting computation.If the machine halts,the output ofthe computation is thefinite string written on the output tape.Else,the output is either afinite string or an infinite sequence written on the output tape as a result of a never ending process.This leads to consider{0,1}≤ωas the output space.We introduce the following maps for the behaviour of machines at a given stage of the computation.DEFINITION2.1.Let M be a Turing machine.M(p)[t]is the current output of M on input p at stage t.Notice that M(p)[t]does not require that the computation on input p halts.DEFINITION2.2.Let M be a prefix machine.M(p)[t]is the current output of M on input p at stage t if it has not read beyond the end of p.Otherwise,M(p)[t]↑. Again,notice that M(p)[t]does not require that the computation on input p halts.Observe that depending on whether M is a prefix machine or not M(p)[t]refers to Definition2.1or2.2.In both cases M(p)[t]is a partial recursive function with recursive domain.136V.BECHER AND S.FIGUEIRA REMARK2.4.If M is monotone then M(p)[t] M(p)[t+1],in case M(p) [t+1]↓.If M is a prefix machine then:1.If M(p)[t]↑then M(q)[u]↑for all q p and u≥t.2.If M(p)[t]↓then M(q)[u]↓for any q p and u≤t.Also,if at stage t,Mreaches a halting state,then M(p)[u]↓=M(p)[t]for all u≥t.We introduce maps for the possibly infinite computations on a monotone machine (resp.prefix monotone machine).In this work we restrict ourselves to possibly infinite computations which read justfinitely many symbols from the input tape. DEFINITION2.41.Let M be a Turing machine(resp.prefix machine).The input/output behaviour of M for halting computations is the partial recursive map M:{0,1}∗→{0,1}∗given by the usual computation of M,i.e.M(p)↓iff M enters into a halting state on input p(resp.iff M enters into a halting state on input p without reading beyond p).If M(p)↓then M(p)=M(p)[t]for some stage t at which M entered a halting state.2.Let M be a monotone machine(resp.prefix monotone machine).The in-put/output behaviour of M for possibly infinite computations is the map M∞:{0,1}∗→{0,1}≤ωgiven by M∞(p)=lim t→∞M(p)[t],where M(p)[t] is as in Definition2.1(resp.Definition2.3).In case M∞(p)∈{0,1}∗we say M∞(p)↓and otherwise M∞(p)↑.Observe that M∞extends M,because if the machine M halts on input p,then M∞(p)=lim t→∞M(p)[t]=M(p).REMARK2.5.1.If U is any universal Turing machine with the ability of overwriting the out-put then by Shoenfield’s Limit Lemma(Shoenfield,1959)it follows that U∞computes all∅ -recursive functions.2.Although Shoenfield’s Limit Lemma insures that for any monotone machine M,M∞:{0,1}∗→{0,1}∗is recursive in∅ ,not every∅ -recursive function can be computed in the limit by a monotone machine.One counterexample is the characteristic function of the halting problem.3.An example of a non-recursive function that is obtainable via an infinite com-putation on a monotone machine is the Busy Beaver function in unary notation bb:N→1∗,where bb(n)is the maximum number of1’s produced by any Turing machine with n states which halts with no input.bb is∅ -recursive andKOLMOGOROV COMPLEXITY FOR POSSIBLY INFINITE COMPUTATIONS137 bb(n)is the output of a non halting computation which on input n,it simulates every Turing machine with n states and for each one that halts it updates,if necessary,the output with more1’s.PROPOSITION2.6Let M be a prefix monotone machine.1.domain(M)is closed under extensions and its syntactical complexity is 01.2.domain(M∞)is closed under extensions and its syntactical complexity is 01.Proof.Item1is trivial.For item2,observe that M∞(p)↓⇔∀t M on input p does not read p0and does not read p1at stage t.Clearly,domain(M∞)is closed under extensions since if M∞(p)↓then M∞(q)↓=M∞(p)for every q p.REMARK2.7.Let M be a prefix monotone machine.An alternative and equivalent definition of M and M∞would be to consider them with prefix-free domains (instead of closed under extensions).–M(p)↓iff at some stage t M enters a halting state having read exactly p.If M∞(p)↓then its value is lim t→∞M(p)[t].–M∞(p)↓iff∃t at which M has read exactly p and for every t >t,M does not read p0nor p1.If M∞(p)↓then its value is lim t→∞M(p)[t].All properties of the complexity functions we study in this paper hold for this alternative definition.Wefix an effective enumeration of all tables of instructions.This gives an effective (M i)i∈N.Wefix the usual(prefix)monotone universal machine U,which definesthe functions U(0i1p)=M i(p)and U∞(0i1p)=M∞i (p)for halting and possiblyinfinite computations respectively.Recall that U∞is an extension of U.We also fix U∅ a monotone universal machine with an oracle for∅ .2.2.P ROGRAM-S IZE C OMPLEXITIESLet us consider inputs as programs.The Kolmogorov or program-size complexity (Kolmogorov,1965)relative to a Turing machine M is the function K M:{0,1}∗→N which maps a string s to the length of the shortest programs that output s.Thatis,K M(s)=min{|p|:M(p)=s}if s is in the range of M ∞otherwiseSince the subscript M can be any machine,even one equipped with an oracle,this is a definition of program-size complexity for both effective or relative computability.138V.BECHER AND S.FIGUEIRA In case M is a prefix machine we denote it H M rather than K M and we call it prefix complexity.In general,these program-size complexities are not recursive.The invariance theorem(Kolmogorov,1965)states that the universal Turing machine U is asymptotically optimal for program-size complexity,i.e.,∀Turing machine M∃c∀s K U(s)≤K M(s)+c.For any pair of asymptotically optimal machines M and N there is a constant c such that|K M(s)−K N(s)|≤c for every string s.Thus,program-size complexity on asymptotically optimal machines counts as an absolute measure of complexity, up to an additive constant.The same holds for prefix machines(Chaitin,1975; Levi,1974).We shall write K(resp.H)for K U(resp.H U)where U is some universal Turing (resp.universal prefix)machine.The complexity for a universal machine(resp. prefix machine)with oracle A is notated as K A(resp.H A).As expected,the help of oracles leads to shorter programs up to an additive constant(cf.Propositions2.10and2.11).2.3.P ROGRAM-S IZE C OMPLEXITY FOR P OSSIBLY I NFINITE C OMPUTATIONSLet M be a monotone machine,and M,M∞the respective maps for input/output behaviour of M for halting computations and possibly infinite computations(see Definition2.4).DEFINITION2.8.K∞M:{0,1}≤ω→N is the program-size complexity for functions M∞:K∞M(x)=min{|p|:M∞(p)=x}if x is in the range of M∞∞otherwiseFor the universal U we drop subindexes and we simply write K∞(resp.H∞).Because the set of all tables of instructions is r.e.,the Invariance Theorem holds for K∞:for every monotone machine M there is a c such that∀s∈{0,1}≤ωK∞(s)≤K∞M(s)+c.The Invariance Theorem also holds for H∞.REMARK2.9.From Remark2.5it is immediate that if U is a Turing machine with the ability of overwriting the output,that is,U is not monotone,K∞coincides with K∅ ,up to an additive constant.We mention some known results that will be used in the next sections.KOLMOGOROV COMPLEXITY FOR POSSIBLY INFINITE COMPUTATIONS139 PROPOSITION2.10.1.∃c∀s∈{0,1}∗K(s)≤|s|+c.2.∃c∀s∈{0,1}∗K∅ (s)−c<K∞(s)<K(s)+c.3.∀n∃s∈{0,1}∗of length n such that K(s)≥n.The same holds for K∅ andK∞.Proof.Item1follows directly from definition and the Invariance Theorem for K.For thefirst inequality of item2,observe that any unending computation that out-puts justfinitely many symbols can be simulated on a universal machine equipped with oracle∅ ,by increasing number of steps.At each step,the simulation polls the oracle to determine whether the computation would output more symbols or not. The simulation halts when there is no more output left.Item3holds because there are2n strings of length n,but2n−1programs of length less than n.PROPOSITION2.11.1.(Chaitin,1975)∃c∀s∈{0,1}∗H(s)≤H(|s|)+|s|+c.In particular,∃c∀s∈{0,1}∗H(s)≤|s|+c=2|s|+c.2.Items2and3of Proposition2.10are still valid considering H,H∞and H∅(see Becher et al.,2001).3.Oscillations of K∞In this section we study some properties of the complexity function K∞and compare them with K and K∅ .We know K∅ ≤K∞≤K up to addi-tive constants.The following results show that K∞is really in between K∅ and K.There are strings that separate the three complexity functions K,K∅ and K∞arbitrarily:THEOREM3.1.For every c there is a string s∈{0,1}∗such thatK∅ (s)+c<K∞(s)<K(s)−c.Proof.We know that for every n there is a string s of length n such that K(s)≥n.Let d n be thefirst string of length n in the lexicographic order satisfying this inequality,i.e.d n=min{s∈{0,1}n:K(s)≥n}.Let f:N→{0,1}∗be any recursive function with infinite range,and consider a machine C which on input i does the following:140V.BECHER AND S.FIGUEIRA j:=0RepeatWrite f(j)Find a program p,|p|≤2i,such that U(p)=f(j)j:=j+1The machine C on input i outputs(in the limit)c i=f(0)f(1)...f(j i)where K(f(j i))>2i and∀z,0≤z<j i:K(f(z))≤2i.For each i,we define e i=d i c i.Let usfix k and see that there is an i1such that∀i≥i1:K∞(e i)−K∅ (e i)>k. On the one hand,we can compute d i from i and a minimal program p such that U∞(p)=e i by simulating U(p)until it outputs i bits.If we code the input as ip we obtaini≤K(d i)≤K∞(e i)+2|i|+O(1).(1)On the other hand,with the help of the∅ oracle,we can compute e i from i.HenceK∅ (e i)≤|i|+O(1).(2)From(1)and(2)we have K∞(e i)−K∅ (e i)+O(1)≥i−3|i|and then,there is i1such that for all i≥i1,K∞(e i)−K∅ (e i)>k.Let us see now that there is i2such that∀i≥i2:K(e i)−K∞(e i)>k.Given i and a shortest program p such that U(p)=e i we construct a machine that computes f(j i).Indeed,if we code the input as ip,the following machine does the work: Obtain iCompute e:=U(p)s:=e ij:=0Repeats:=s f(j)If s=e then write f(j)and haltj:=j+1Hence,for all i2i<K(f(j i))≤K(e i)+2|i|+O(1).(3)Using the machine C we can construct a machine which,via an infinite computation, computes e i from a minimal program p such that U(p)=d i.Then,for every iK∞(e i)≤K(d i)+O(1)≤i+O(1).(4)KOLMOGOROV COMPLEXITY FOR POSSIBLY INFINITE COMPUTATIONS141 From(3)and(4)we have K(e i)−K∞(e i)+O(1)>i−2|i|so the difference between K(e i)and K∞(e i)can grow arbitrarily as we increase i.Let i2be such that for all i≥i2,K(e i)−K∞(e i)>k.Taking i0=max{i1,i2},we obtain∀i≥i0:K∅ (e i)+k<K∞(e i)<K (e i)−k.The three complexity functions K,K∅ and K∞get close infinitely many times. THEOREM3.2.There is a constant c such that for every n:∃s∈{0,1}n:|K∅ (s)−K∞(s)|≤c∧|K∞(s)−K(s)|≤c.Proof.Let s n be of length n such that K∅ (s n)≥n.From Proposition2.10, there exist c1,c2and c3such thatn≤K∅ (s n)≤K∞(s n)+c1≤K(s n)+c1+c2≤n+c1+c2+c3. Take c=c1+c2+c3.For infinitely many strings,K and K∞get close but they separate from K∅ as much as we want.THEOREM3.3.There is a constant c such that for all m∃s∈{0,1}∗:K(s)−K∅ (s)>m∧|K∞(s)−K(s)|<c.Proof.We know that#{s∈{0,1}n+2|n|:K(s)<n}<2n and then#{s∈{0,1}n+2|n|:K(s)≥n}>2n+2|n|−2n.Let S n={|w|w:w∈{0,1}n}.Notice that,if s∈S n,|s|=n+2|n|.Clearly, #S n=2n.Assume by contradiction that there is n such that S n∩{s∈{0,1}n+2|n|: K(s)≥n}=∅.Then2n+2|n|≥#S n+#{s∈{0,1}n+2|n|:K(s)≥n}>2n+2|n| which is impossible.For every n,let us define s ns n=min{s∈S n:K(s)≥n}.(5) Given a minimal program p such that U∞(p)=s n,we can compute s n in an effective way.The idea is to take advantage of the structure of s n to know when U∞stops writing in its output tape:we simulate U∞(p)until we detect¯n and we continue the simulation of U∞until we see it writes exactly n more bits.Then for each n,K(s n)≤K∞(s n)+O(1)and from Proposition2.10we have that for all n the difference|K(s n)−K∞(s n)|is bounded by a constant.142V.BECHER AND S.FIGUEIRA Using the∅ oracle,we can compute s n from n.Hence K∅ (s n)≤|n|+O(1). From(5)we conclude K(s n)−K∅ (s n)+O(1)≥n−|n|.Thus,the difference between K(s n)and K∅ (s n)can be made arbitrarily large.Infinitely many times K∞and K∅ get close but they separate from K arbitrarily.THEOREM3.4.There is a constant c such that for each m∃s∈{0,1}∗:K(s)−K∞(s)>m∧|K∞(s)−K∅ (s)|<c.Proof.As in the proof of Theorem3.1,consider a recursive f with infinite range,let c n=n f(0)f(1)...f(j n),and slightly modify the machine C such that on input i,itfirst writes i and then it continues writing f(j)until itfinds a j i such that K(f(j i))>2i and∀z,0≤z<j i:K(f(z))≤2i.Thus,given str(n),we can compute n and then c n in the limit.Hence for every nK∞(c n)≤|str(n)|+O(1).(6)Given an∅ oracle minimal program for c n,we can compute str(n)in an oracle machine.Then for every nK∅ (str(n))≤K∅ (c n)+O(1).(7)We define m n=min{s∈{0,1}n:K∅ (s)≥n}and s n=c str−1(m n).From(7)we known≤K∅ (m n)≤K∅ (s n)+O(1)(8)and from(6)we haveK∞(s n)≤|m n|+O(1).(9)From(8)and(9)we obtain K∞(s n)−K∅ (s n)≤O(1)and by Proposition2.10 we conclude that for all n,|K∞(s n)−K∅ (s n)|≤O(1).In the same way as we did in Theorem3.1,we construct an effective machine that outputs f(j n)from a shortest program such that U(p)=c n,but in this case the machine gets n from the input itself(we do not need to pass it as a distinct parameter).Hence for all n,2n<K(f(j n))≤K(c n)+O(1)and in particular for n=str−1(m n) we have2str−1(m n)<K(s n)+O(1).Since for each string s,|s|≤str−1(s)we have2|m n|<K(s n)+O(1).From(9)and recalling that|m n|=n,we have K(s n)−K∞(s n)+O(1)>n.Thus,the difference between K(s n)and K∞(s n) grows as n increases.KOLMOGOROV COMPLEXITY FOR POSSIBLY INFINITE COMPUTATIONS143 It is known that the complexity function K is smooth in the length and lexico-graphic order on{0,1}∗,i.e.|K(str(n))−K(str(n+1))|=O(1).The following result holds for K∞.PROPOSITION3.5.For all n|K∞(str(n))−K∞(str(n+1))|≤2K(|str(n)|)+O(1).Proof.Consider the following monotone machine M with input pq:Obtain y=U(p)Simulate z=U∞(q)till it outputs y bitsWrite str(str−1(z)+1)Let p,q∈{0,1}∗be such that U(p)=|str(n)|and U∞(q)=str(n).Then, M∞(pq)=str(n+1)and K∞(str(n+1))≤K∞(str(n))+2K(|str(n)|)+O(1).Similarly,if M above instead of writing str(str−1(z)+1),it writes str(str−1(z)−1),we concludeK∞(str(n))≤K∞(str(n+1))+2K(|str(n+1)|)+O(1).Since,|K(str(n))−K(str(n+1))|≤O(1),we have|K∞(str(n))−K∞(str(n+1))|≤2K(|str(n)|)+O(1).Loveland and Meyer(1969)have given a necessary and sufficient condition to characterize recursive sequences,based on the program-size complexity of their initial segments.They showed that a sequence A∈{0,1}ωis recursive iff ∃c∀n K(A n)≤K(n)+c.In this sense,the recursive sequences are those whose initial segments have minimal K complexity.We show that the advan-tage of K∞over K can be seen along the initial segments of every recursive sequence:if A∈{0,1}ωis recursive then there are infinitely many n’s such that K(A n)−K∞(A n)>c,for an arbitrary c.PROPOSITION3.6.Let A∈{0,1}ωbe a recursive sequence.ThenK(A n)−K∞(A n)=∞.lim supn→∞Proof.Let f:N→{0,1}be a total recursive function such that f(n)is the n-th bit of A.Let us consider the following monotone machine M with input p:144V.BECHER AND S.FIGUEIRA Obtain n:=U(p)Write A (str−1(0n)−1)For s:=0n to1n in lexicographic orderWrite f(str−1(s))Search for a program p such that|p|<n and U(p)=sIf U(p)=n,then M∞(p)outputs A k n for some k n such that2n≤k n<2n+1, since for all n there is a string of length n with K-complexity greater than or equal to n.Let usfix n.Then,K∞(A k n)≤|n|+O(1).However,K(A k n)+O(1)≥n, because we can compute thefirst string of length n in the lexicographic order with K-complexity≥n from a program for A k n.Hence,for each n,K(A k n)−K∞(A k n)+O(1)≥n−|n|.4.Program-Size Complexity for Possibly Infinite Computations on PrefixMonotone MachinesWe show that Theorems3.1and3.3are valid for H∞.THEOREM4.1.For every c there is a string s such thatH∅ (s)+c<H∞(s)<H(s)−c.Proof.The proof is essentially the same as that of Theorem3.1but using prefix monotone machines.Let c n=f(0)f(1)...f(j n)and slightly change the instruc-tions of machine C putting H(f(j n))>3n and∀z,0≤z<j n:H(f(z))≤3n.Let d n=min{s∈{0,1}n:H(s)≥n}and e n=d n c n.Assume p is a shortest program such that U∞(p)=e i.Consider the effective machine which on input ip does the following:Obtain iSimulate x i=U∞(p)until it outputs i bitsPrint x and haltThen,we havei≤H(d i)≤H∞(e i)+2|i|+O(1).(10) If we code the input of the oracle computation of the proof of Theorem3.1by duplicating the bits(now we cannot use just|i|bits to code i),inequality(2) becomesH∅ (e i)≤2|i|+O(1).(11) From(10)and(11)we have H∞(e i)−H∅ (e i)+O(1)≥i−4|i|,and so we can make the difference between H∞(e i)and H∅ (e i)as large as we want.To show thatKOLMOGOROV COMPLEXITY FOR POSSIBLY INFINITE COMPUTATIONS145 the difference between H(e i)and H∞(e i)can also be made arbitrarily large,we replace(3)by3i<H(f(j i))≤H(e i)+2|i|+O(1)(12)and recalling that for each string s,H(s)≤2|s|+O(1),inequality(4)is replaced byH∞(e i)≤H(d i)+O(1)≤2i+O(1).(13)From(12)and(13)we get H(e i)−H∞(e i)+O(1)>i−2|i|.For infinitely many strings,H and H∞get close but they separate from H∅ as much as we want:THEOREM4.2.There is a constant c such that for all m∃s∈{0,1}∗:H(s)−H∅ (s)>m∧|H∞(s)−H(s)|≤c.Proof.The idea of the proof is the same as the one in Theorem3.3.We redefine s n(see(5)):s n=min{s∈S n:H(s)≥n}.(14) We consider the same program as in the proof of Theorem3.3but using prefix monotone machines.Identically we obtain H(s n)≤H∞(s n)+O(1)and from Proposition2.11we have|H(s n)−H∞(s n)|≤O(1).Instead of K∅ (s n)≤|n|+O(1) we obtain H∅ (s n)≤2|n|+O(1)and from(14)we conclude H(s n)−H∅ (s n)≥n−2|n|+O(1).Thus,the difference between H(s n)and H∅ (s n)grows as n increases.We can show the following weaker version of Theorem3.4for H∞. PROPOSITION4.3.There is a sequence(s n)n∈N such thatH(s n)−H∞(s n)=∞and|H∞(s n)−H∅ (s n)|≤H(n)+O(1).limn→∞Proof.The idea is similar to the proof of Theorem3.4,but making j i such that H(f(j i))>3i and∀z,0≤z<j i:H(f(z))≤3i.We replace(6)byH∞(c n)≤H(str(n))+O(1)(15)146V.BECHER AND S.FIGUEIRA since there is a machine that via an infinite computation computes n and c n from a shortest program p such that U(p)=str(n).There is a machine with oracle∅ that computes str(n)from a minimal oracle program for c n.Then,restating(7),we have for every nH∅ (str(n))≤H∅ (c n)+O(1).(16)Let m n=min{s∈{0,1}n:H∅ (s)≥n}and s n=c str−1(m n).From(15)and(16) we have H∞(s n)−H∅ (s n)≤H(m n)−H∅ (m n)+O(1)≤H(m n)−n+O(1) and,since H(m n)≤H(|m n|)+|m n|+O(1)we conclude H∞(s n)−H∅ (s n)≤H(n)+O(1).We can construct an effective machine that computes f(j n)from a minimal program for U which outputs c n.From(15)we have H(s n)−H∞(s n)+ O(1)>3n−H(m n).Since for all n,H(m n)≤2|m n|+O(1)=2n+O(1),we get H(s n)−H∞(s n)+O(1)>n and hence the difference can be made arbitrarily large.Proposition3.5for H∞is still valid considering H(|str(n)|)+O(1)as the upper bound.It is easy to see that the recursive sequences in{0,1}ωhave minimal H complexity,i.e.,for any recursive A∈{0,1}ω∃c∀n H(A n)≤H(n)+c.It is easy to see that the analog of Proposition3.6is also true for H∞.Wefinally prove some properties that are only valid for H∞. PROPOSITION4.4.For all strings s and t1.H(s)≤H∞(s)+H(|s|)+O(1).2.H∞(ts)≤H∞(s)+H(t)+O(1).3.H∞(s)≤H∞(st)+H(|t|)+O(1).4.H∞(s)≤H∞(st)+H∞(|s|)+O(1).Proof.1.Let p,q∈{0,1}∗be such that U∞(p)=s and U(q)=|s|.Then there isa machine thatfirst simulates U(q)to obtain|s|,then it starts a simulation ofU∞(p)writing its output on the output tape,until it has written|s|symbols,and then halts.2.Let p,q∈{0,1}∗be such that U∞(p)=s and U(q)=t.Then thereis a machine thatfirst simulates U(q)until it halts and prints U(q)on the output tape.Then,it starts a simulation of U∞(p)writing its output on the output tape.3.Let p,q∈{0,1}∗be such that U∞(p)=st and U(q)=|t|.Then there isa machine thatfirst simulates U(q)until it halts to obtain|t|.Then it starts aKOLMOGOROV COMPLEXITY FOR POSSIBLY INFINITE COMPUTATIONS147 simulation of U∞(p)such that at each stage n of the simulation it writes the symbols needed to print U(p)[n] (|U(p)[n]|−|t|)on the output tape.4.Consider the following monotone machine:t:=1;v:=λ;w:=λRepeatif U(v)[t]asks for reading then v:=v bif U(w)[t]asks for reading then w:=w bwhere b is the next bit in the inputextend the actual output to U(w)[t] (U(v)[t])t:=t+1If p and q are shortest programs such that U∞(p)=|s|and U∞(q)=st respectively,then we can interleave p and q in a way that at each stage t,v p and w q(notice that eventually v=p and w=q).Thus,this machine will compute s and will never read more than H∞(st)+H∞(|s|)bits. AcknowledgementsThis work is supported by Agencia Nacional de Promoci´o n Cient´ıfica y Tecnol´o gica (V.B.),and by a grant of Fundaci´o n Antorchas(S.F.).ReferencesBecher,V.,Daicz,S.,and Chaitin,G.,2001,“A highly random number,”pp.55–68in Combina-torics,Computability and Logic:Proceedings of the Third Discrete Mathematics and Theoretical Computer Science Conference(DMTCS’01),C.S.Calude,M.J.Dineen,and S.Sburlan,eds., London:Springer-Verlag.Chaitin,G.J.,1975,A theory of program-size formally identical to information theory,Journal of the ACM22,329–340.Chaitin,G.,1976a,“Algorithmic entropy of sets,”Computers&Mathematics with Applications2, 233–245.Chaitin,G.J.,1976b,“Information-theoretical characterizations of recursive infinite strings,”Theoretical Computer Science2:45–48.Ferbus-Zanda,M.and Grigorieff,S.,2004,“Kolmogorov complexities K max,K min”(submitted). Katseff,H.P.and Sipser,M.,1981,“Several results in program-size complexity,”Theoretical Computer Science15,291–309.Kolmogorov,A.N.,1965,“Three approaches to the quantitative definition of information,”Problems of Information Transmission1,1–7.Levin,L.A.,1974,“Laws of information conservation(non-growth)and aspects of the foundations of probability theory,”Problems of Information Transmission10,206–210.Li,M.and Vit´a nyi,P.1997,An Introduction to Kolmogorov Complexity and its Applications (2nd edition),Amsterdam:Springer.。

Fluent学习经典教材列举G. Falkovich, Fluid Mechanics: A Short Course for PhysicistsL.D. Landau and E.M. Lifshitz, “Fluid Mechanics” - a classicG.K. Batchelor, “An Introduction to Fluid Dynamics” - complements LandauG.B. Whitman; “Linear and Nonlinear Waves” - yet another great oneJ. Lighthill; “Waves in Fluids” - excellent and accessibleU. Frisch; “Turbulence-The Legacy of A.N. Kolmogorov” – classic book on urbulence ala’ K41 A. Townsend; “The Structure of Turbulent Shear Flow” –classic book on urbulence in real systems上⾯诸位推荐流体⼒学教材若⼲，我另外推荐⼀本可能更侧重计算流体⼒学(CFD)的书：Computational Methods for Fluid Dynamics 2002 Joel Henry Ferziger, Milovan Peri?这本书不算太旧，作者是斯坦福计算流体⼒学专业的教授，公认的计算流体⼒学⽅⾯的专家，springer出品，质量应该不会太差。

推荐⼏本我⾃⼰学的书吧。

我个⼈⾮常反感将流体⼒学讲成数学课的做法。

基础书：1.Frank White, Fluid Mechanics2.J.D. Anderson, Computational Fluid Dynamics3.吴⼦⽜，空⽓动⼒学4.朱克勤，许春晓，粘性流体⼒学进阶书：1.Toro, Riemann Solvers and Numerical Methods for Fluid Dynamics2.D.C. Wilcox, Turbulence Modelling for CFD3.Pope, Turbulent Flows我来说⼀下，也是⼀个参考，也希望⼤家尽快上⼿，免得⾛弯路。

二氧化钛纳米管的制备及应用综述段秀全盖利刚周国伟（山东轻工业学院化学工程学院，山东济南250353）摘要：TiO2纳米管具有较大的直径和较高的比表面积等特点，在微电子、光催化和光电转换等领域展现出良好的应用前景。

本文对TiO2纳米管材料的合成方法、形成机理及应用研究进行了综述。

关键词：TiO2纳米管；制备；应用中图分类号: O632.6 文献标识码: APreparation and Application of TiO2 nanotubesDUAN Xiu-quan, GAI Li-gang, ZHOU Guo-wei(School of Chemical Engineering, Shandong Polytechnic University, Jinan, 250353, China) Abstract: TiO2nanotubes have wide applications in microelectronics, photocatalysis, and photoelectric conversions, due to their relatively larger diameters and higher specific surface areas. In this paper, current research progress relevant to TiO2nanotubes has been reviewed including synthetic methods, formation mechanisms, and potential applications.Keywords: TiO2 nanotubes; preparation; application自1991年日本NEC公司Iijima[1]发现碳纳米管以来，管状结构纳米材料因其独特的物理化学性能，及其在微电子、应用催化和光电转换等领域展现出的良好的应用前景，而受到广泛的关注。

大气光学湍流强度估算和预报方法研究吴晓庆【摘要】本文简述利用常规气象参数,基于Monin-Obukhov相似理论估算近地面Cn2和基于Tatarski公式估算高空Cn2的方法和估算结果,并给出了利用中尺度气象模式WRF开展的预报Cn2的研究成果.构建合适的光学湍流外尺度参数化公式,进行中尺度模式与微尺度模式嵌套,开展光学湍流参数化新方法的研究,是今后提高光学湍流估算和预报精度努力的方向.【期刊名称】《安徽师范大学学报（自然科学版）》【年(卷),期】2016(039)006【总页数】5页(P511-515)【关键词】大气光学湍流;估算;预报【作者】吴晓庆【作者单位】中国科学院安徽光学精密机械研究所中国科学院大气成分与光学重点实验室,安徽合肥230031【正文语种】中文【中图分类】TN24湍流是近百年来物理学中尚未解决好的一个极为艰难的重大课题.从1883年Reynolds开始现代湍流研究以来，对湍流的认识在不断深化，一些杰出科学家留下了他们的足迹.如Taylor(1921)的涡模型[1]、Prandtl(1925年)的混合长模型[2]、Von Karman(1930年)相似模型[3]、Richardson(1922年)多尺度级串模型[4]、Kolmogorov(1941年)局地各向同性模型[5]、周培源(1945年)湍流动力学方程[6]、Lorentz(1963年)发现奇异吸引子[7]以及混沌现象等是这一期间研究湍流的最主要成果.目前大多数人的观点是：湍流是多尺度有结构的不规则的流体运动，其基本物理特性可由Navier-Stokes方程来描述.随着计算机的迅速发展，湍流的数值模拟逐渐兴起.能分辨所有尺度湍涡的数值模拟称为直接数值模拟(Direct Numerical Simulation, DNS).DNS方法，由于不需作简化和假设，直接求解已知初始条件和边界条件的Navier-Stokes方程组，成为研究低雷诺数、简单几何边界湍流的主要工具之一.Coleman(1990)等使用DNS揭示了Ekman层的湍流特征[8].受限于目前计算机的容量和速度，我们还不能对104量级以上的高Reynolds数湍流进行直接数值模拟.作为DNS方法的一种折中，大涡数值模拟(large eddy simulation, LES)方法，采用合适滤波器，将大尺度湍涡和小尺度湍涡分开，对Navier-Stokes方程做过滤运算，通过建立亚格子应力模型(过滤掉的小尺度湍涡对大尺度湍涡的作用称为亚格子应力)，来模拟包含大于过滤尺度的所有含能大尺度运动.尽管LES方法比DNS方法节省很大的计算量，而且在大气边界层等领域展现不俗的研究潜力[9-13]，但仍受到计算机容量和速度的限制，LES模拟Reynolds数较高的对流边界层以及复杂边界条件下的湍流，减少数值模拟湍流与实际湍流之间的误差仍需要相当长的时间.湍流对大气中声、光和其它电磁波的传播产生重要的影响，原因是大气中存在小尺度折射率起伏，我们称为大气光学湍流.大气折射率结构常数是描述大气光学湍流的重要参数，从某种意义上说，知道了时空分布，就可以计算出大气光学湍流对光电系统的影响.仪器测量和模式估算是获取时空分布最常用的两种方法.因受人力、物力所限难以在全国大范围内进行大气光学湍流较长时间的现场测量，若实现用常规气象参数的方法估算高空光学湍流，则可利用地域广数据量多的常规气象资料，再结合光学湍流现场观测数据的检验，就可获得在地域、气候等方面具有代表性地区可靠的高空光学湍流数据.如何用常规气象参数估算光学湍流，反映的是平均气象场与随机湍流场的内在联系，开展这方面工作可以加深大气湍流自身规律如湍流产生机制等物理问题的研究.光学湍流预报涉及多学科如大气科学(包括气象学、大气物理)、计算数学和计算机计术、光学工程(包括天文选址、光传输和光通讯)、湍流测量技术等其它学科和领域的交叉和融合.这种多学科的交叉和融合，既是挑战也是机遇.近几年我们开展了用常规气象参数进行大气光学湍流强度估算和预报方法研究.本文简述基于Monin-Obukhov相似理论开展的近地面的估算结果；基于Tatarski公式和气象探空数据，开展的高空的初步研究；以及利用中尺度气象模式WRF开展的预报的研究.相似理论是研究边界层湍流模式的基石.我们运用Monin-Obukhov相似理论[14]，用Bulk方法，通过测量两高度层上的风速、温度、绝对湿度差值，估算出湍流通量，得到折射率结构常数.式中L是Monin-Obukhov长度，△T为两层的温差，△q是两层湿度差，rTq是温湿相关项系数.系数A、B分别为分别是温度结构常数、风速、温度的无量纲普适函数.茂名博贺海洋气象科学试验基地位于广东省西南部(21°27′N，111°18′E)，南濒南中国海.我们研制的移动式大气参数测量系统安装在岸基观测站.图1是模式估算的与温度脉动仪测量的的比对.模式输入的常规气象参数是两层气温、相对湿度、风速.z1=0.50m，z2=2.15m.测量时间2012年9月26日至10月19日共24天.模式估算和温度脉动仪测量在量级和变化趋势基本一致.但夜晚稳定的大气条件下，模式估算精度有待深入研究.国内外有许多学者提出了廓线模式.这类模式是在大量观测数据基础上总结出的经验公式，基本上代表的是一个统计平均的结果.模式中的参数仅含有高度或少量的气象参数.如SLC模式、AFGL AMOS 夜晚模式、CLEAR Ⅰ夜晚模式、Hufnagel-Valley(5/7)模式、冬季兴隆廓线模式等，限于篇幅，其表达式这里不再赘述，参见参考文献[15].图2是建立高空大气光学湍流模式方框图.Tatarski公式形式为：这里,T是绝对气温(K)，P是气压(hPa)，γa是干空气绝热递减率(9.8×10-3-1),h是高度(m)，L0是湍流外尺度.Dewan在实验数据基础上将看作是风切变的函数：对流层平流层S是风剪切量.与Dewan类似的HMNSP99外尺度参数化公式增加了温度梯度.对流层平流层外尺度经验公式还有Coulman公式.我们通过测量30km以下的温度、湿度、气压、风速风向和，对常规气象参数估算的与实测的进行比对.图3是在合肥进行的温度、风速、风向廓线的一次探空实例，测量时间为2014年5月7日21:48:58-23:46:34.图4是四种外尺度模式(Dewan、HMNSP99、Sterengorg、Coulman)估算的结果与测量值的比较[16].从变化趋势和量级看，HMNSP99的外尺度模式估算的与测量值接近.文献16对现有的典型模式进行比对.给出了四种廓线模式(SLC模式、AFGL AMOS 夜晚模式、C LEARⅠ夜晚模式、Hufnagel模式)估算的，和四种外尺度模式(Dewan、HMNSP99、Sterengorg、Coulman)估算的，并与温度脉动探空仪测量的进行了比较，归纳出的实测值和模式值的一些共同特点和差异，指出选择合适的外尺度模式是用Tatarski公式估算的关键.大气中包含有大、中、小尺度的大气运动系统.其中“中尺度系统”的概念是在50年代初随着气象雷达和加密观测网的发展而形成的.它一般是指时间和水平空间尺度比常规探空网的时空密度小，但比积云单体的生命期及空间尺度大得多的一种系统.中尺度天气预报模式是通过一系列方程模拟反映大气参数如温度、气压、水汽、风速等随时间的演变.模式内的大气三维空间被分割成一系列网格点阵，每个格点上的气象参数值代表了当时大气的状况.网格点数量愈多，模式分辨率愈高，空间分辨率提高一倍，所需计算量将提高16倍.从数学角度，气象模式就是一组数学物理方程，在给定初始条件和边界条件下，就可以得到这组数学物理方程的解.湍流能量从大尺度涡旋向小尺度级串，为人们定性和定量地认识湍流的多尺度现象,从中尺度天气预报模式估算小尺度湍流成为可能.中尺度气象模式最具代表性的是MM5(The Fifth-Generation Mesoscale Model)和WRF(Weather Research and Forecast).两种模式源代码开放，从相关网站可获取全球气象观测基础数据库、全球高程数据库、全球土壤和植被系数数据库等模式运行所需的基础数据.Coulman(1986)[17]最早提出有可能从气象参数预报大气光学湍流.Bougeault(1995)[18]则采用流体静力假设的中尺度模式PERIDOT，法国探空网提供初值条件，首次实现了使用中尺度气象模式估算和预报法国境内Lachens山附近视宁度.2007年我们[19]国内率先开展了利用MM5预报高空的初步研究，在此基础上进行了WRF模式预报光学湍流的进一步研究[20-22].图5是我们运用WRF估算云南天文台高美古站光学湍流强度的一次实例[22].丽江高美古观测站(100.03°E,26.69°N)海拔高度约3227m.模拟平台采用Lenovo Product系列台式计算机，4核CPU，4G内存和1T容量硬盘.操作系统采用Linux架构下的Ubuntu(10.04 LTS)系统.采用3层网格嵌套，东西方向格点数从外到内分别为65，91，124；南北方向格点数从外到内分别为49，61，97；网格分辨率从外到内分别为36，12，4 km；静态地形数据的分辨率为10＇，5＇，2＇；投影方式采用lambert正型投影；输入的初始场资料为再分析场数据(FNL)，分辨率为1°×1°.顶层气压设置为10 hPa.基本模拟参数设置见表1.WRF模拟的气温、风速廓线与我们自行研制的湍流气象探空仪测量的结果基本一致.近地面模式估算和温度脉动仪测量在量级和变化趋势基本一致.对于复杂的下垫面，夜晚稳定的大气条件，选择合适的相似性函数，提高模式估算精度有待深入研究. 采用Dewan、HMNSP99、Coulman和Sterenborg四种外尺度模式对值进行估算，并与探空测量的值进行了比较.HMNSP99模式估算的值和测量值在量级和变化趋势上相接近.WRF模式模拟光学湍流强度与实测结果基本一致.构建合适的光学湍流外尺度参数化公式，进行中尺度模式与微尺度模式嵌套，开展光学湍流参数化新方法的研究，是今后提高光学湍流估算和预报精度努力的方向.【相关文献】[1] TYLOR G I. Diffussion by continuous movements[J]. Proc London Math Soc,1921,(20):196-211.[2] PRANDTL L. Bericht uber untersuchungen zur ausgebildeten Turbulenz[J]. Zs angew Math Mech， 1925,(5):136-139.[3] von Karman T. Mechanische anlichkeit und turbulenz[J]. Nachr Ges Wiss Gottingen, Math-Phys K1, 1930,(3)：51-76.[4] RICHARDSON L F. Weather prediction by numerical process[M]. Cambridge university press, 1922.Cambridge[5] KOLOMOGOROV A N. The local structure of turbulence in incompressible viscous fluid for very large Reynolds number[J]. Dokl Akad Nauk SSSR, 1941,30:9-13(Reprinted in Proc，Royal Soc， Lond A, 1991,9-13)[6] CHOU P Y. Pressure flow of a turbulent fluid between two infinite parallel planes[J]. Quanterly Appl Math, 1945,3(3):198-209.[7] LORENTZ E N. Deterministic nonperiodic flow[J]. J Atmos Sci， 1963,20,130-141.[8] COLEMAN G N, FERZIGER J H, SPALART P R. A numerical study of the turbulent Ekman layer[J]. J Fluid Mech, 1990,213,313-348.[9] 蒋维楣，苗世光.大涡模拟与大气边界层研究-30年回顾与展望[J]，自然科学进展，2004,14(1)：11-19.[10] MASON P J. Large eddy simulation: A critical review of the technique[J]. Quart J RoyMeteor Soc, 1994，120：1-26.[11] MOENG C H. Large eddy simulation of atmospheric boundary layers[M]. Clear and Cloudy Boundary Layers, A A M Holtslag and P G Duynkerke, Eds. Royal Netherlands Academy of Sciences, 1998：67-83.[12] STEVENS B, LENSCHOW D H. Observations,experiments and large-eddy simulation[J]. Bull Ameteor Soc, 2001,82：283-294.[13] 张兆顺，崔桂香，许春晓.走近湍流[J].力学与实践，2002, 24(1)：1-17.[14] 吴晓庆，朱行听，黄宏华，胡顺星.基于Monin-Obukhov相似理论估算近地面光学湍流强度[J].光学学报，2012,32(7)：1-7.[15] 吴晓庆.大气光学湍流、模式与测量技术[J].安徽师范大学学报：自然科学版，2006,29(2)：103-107.[16] 吴晓庆.中尺度气象模式预报大气光学湍流的现状与展望[J].激光与光电子学进展，2016，(已收录).[17] COULMAN C E, ANDRE J C, LACARRERE P， GUILLINGHAM P R. The observations, calculations, and possible forecasting of astronomical seeing[J]. Publ Astron.l Soc Pac, 1986,98:376-387.[18] BOUGEAULT P, CHEN D H, FLEURY B, LAURENT J. Investigation of seeing by means of an atmospheric mesoscale numerical simulation[J]. Appl Opt, 1995,34(18):3481-3488. [19] 许利明，吴晓庆，王英俭.利用中尺度天气预报模式预报大气光学湍流[J].大气与环境光学学报，2008,3(4):270-275.[20] 青春，吴晓庆，李学彬，等.基于天气数值预报模式预报高空光学湍流[J].强激光与粒子束，2015，27(6):1-6.[21] 青春，吴晓庆，李学彬，等.WRF模式估算丽江高美古大气光学湍流廓线[J].中国激光，2015,42(9):1-8.[22] 青春，吴晓庆，李学彬，等.典型地区高空大气光学湍流模拟研究[J]，光学学报，2016,36(5)：1-7.。