Repositorio Institucional
Repositorio Institucional
CONICET Digital
  • Inicio
  • EXPLORAR
    • AUTORES
    • DISCIPLINAS
    • COMUNIDADES
  • Estadísticas
  • Novedades
    • Noticias
    • Boletines
  • Ayuda
    • General
    • Datos de investigación
  • Acerca de
    • CONICET Digital
    • Equipo
    • Red Federal
  • Contacto
JavaScript is disabled for your browser. Some features of this site may not work without it.
  • INFORMACIÓN GENERAL
  • RESUMEN
  • ESTADISTICAS
 
Artículo

Feasible analysis, randomness, and base invariance

Figueira, SantiagoIcon ; Nies, André
Fecha de publicación: 04/2015
Editorial: Springer
Revista: Theory Of Computing Systems
ISSN: 1432-4350
e-ISSN: 1433-0490
Idioma: Inglés
Tipo de recurso: Artículo publicado
Clasificación temática:
Ciencias de la Computación

Resumen

We show that polynomial time randomness of a real number does not depend on the choice of a base for representing it. Our main tool is an ‘almost Lipschitz’ condition that we show for the cumulative distribution function associated to martingales with the savings property. Based on a result of Schnorr, we prove that for any base r, n⋅log2n-randomness in base r implies normality in base r, and that n4-randomness in base r implies absolute normality. Our methods yield a construction of an absolutely normal real number which is computable in polynomial time.
Palabras clave: Base Invariance , Polynomial Time Randomness , Analysis , Normality , Martingales
Ver el registro completo
 
Archivos asociados
Thumbnail
 
Tamaño: 1.037Mb
Formato: PDF
.
Descargar
Licencia
info:eu-repo/semantics/openAccess Excepto donde se diga explícitamente, este item se publica bajo la siguiente descripción: Creative Commons Attribution-NonCommercial-ShareAlike 2.5 Unported (CC BY-NC-SA 2.5)
Identificadores
URI: http://hdl.handle.net/11336/15637
DOI: http://dx.doi.org/10.1007/s00224-013-9507-7
URL: https://link.springer.com/article/10.1007%2Fs00224-013-9507-7
Colecciones
Articulos(OCA CIUDAD UNIVERSITARIA)
Articulos de OFICINA DE COORDINACION ADMINISTRATIVA CIUDAD UNIVERSITARIA
Citación
Figueira, Santiago; Nies, André; Feasible analysis, randomness, and base invariance; Springer; Theory Of Computing Systems; 56; 3; 4-2015; 439-464
Compartir
Altmétricas
 

Enviar por e-mail
Separar cada destinatario (hasta 5) con punto y coma.
  • Facebook
  • X Conicet Digital
  • Instagram
  • YouTube
  • Sound Cloud
  • LinkedIn

Los contenidos del CONICET están licenciados bajo Creative Commons Reconocimiento 2.5 Argentina License

https://www.conicet.gov.ar/ - CONICET

Inicio

Explorar

  • Autores
  • Disciplinas
  • Comunidades

Estadísticas

Novedades

  • Noticias
  • Boletines

Ayuda

Acerca de

  • CONICET Digital
  • Equipo
  • Red Federal

Contacto

Godoy Cruz 2290 (C1425FQB) CABA – República Argentina – Tel: +5411 4899-5400 repositorio@conicet.gov.ar
TÉRMINOS Y CONDICIONES