계산 가능한 수

수학노트
둘러보기로 가기 검색하러 가기

노트

  • There are many more kinds, and Turing claims that there are also computable and non-computable numbers.[1]
  • He defines computable numbers as the real numbers which can be calculated by finite methods.[1]
  • Turing tries to apply this process to the computable numbers and sequences, and fails – thanks to the famous halting problem.[1]
  • The computable numbers are countable and the uncountability of the reals implies that most real numbers are not computable.[2]
  • While the set of computable numbers is countable, it cannot be enumerated by any algorithm, program or Turing machine.[2]
  • In some sense the computable numbers include all numbers which are individually "within our grasp".[2]
  • So the question naturally arises of whether we can dispose of the reals entirely and use computable numbers for all of mathematics.[2]
  • Turing states that computable numbers are those numbers whose decimals can be computed in finite time.[3]
  • (if G of α and not G of β, then α is less than β, then there is a computable limit to the section where a computable number falls.[3]
  • This means a computable bounded sequence of computable numbers might not have a computable limit.[3]
  • Not only do non-computable numbers exist, but in fact they are vastly more abundant than computable numbers.[4]
  • An interesting fact is that the computable numbers are in fact countable, since we may Godel-number the Turing machines which produce them.[5]
  • I suspect that many limiting properties of systems like cellular automata in general correspond to non-computable reals.[6]
  • This is because there is no algorithm to determine which Gödel numbers correspond to Turing machines that produce computable reals.[7]
  • On computable numbers’ (Turing 1937) is taken up with the definition of the ‘Turing machine’, his chosen formal system.[8]
  • Since each description number produces one computable number, these must also be enumerable.[8]
  • The set of computable reals is as numerous as the computer programs, because each computable real needs a computer program to calculate it.[9]
  • You want to cover all the computable reals in the unit interval with a covering which can be arbitrarily small.[9]
  • So you can imagine all the computable reals in a list.[9]
  • This is a bit discouraging to those of us who prefer computable reals to uncomputable ones.[9]
  • To achieve this, a uniform process U needs to be set-up relative to the formalism which is able to compute every computable number.[10]
  • There are only countably many Turing machines, showing that the computable numbers are subcountable.[11]
  • The inverse of this bijection is an injection into the natural numbers of the computable numbers, proving that they are countable.[11]
  • A similar problem occurs when the computable reals are represented as Dedekind cuts.[11]
  • To actually develop analysis over computable numbers, some care must be taken.[11]
  • If so, that we can't provide any examples of non-computable numbers?[12]
  • I removed the following incorrect definition from the main "computable number" page.[13]
  • why ZFC proves that the set of computable numbers is countable".[13]
  • Can computable numbers be used instead of the reals?[13]
  • I would also say the following line In some sense the computable numbers include all numbers which are individually "within our grasp".[13]
  • This paper presents a constructive analysis which is restricted to a countable set of numbers, the field of computable numbers.[14]

소스

  1. ↑ 1.0 1.1 1.2 Alan Turing on Computable Numbers and Computer Programs
  2. ↑ 2.0 2.1 2.2 2.3 Computable number
  3. ↑ 3.0 3.1 3.2 Week 1: Turing's On computable numbers
  4. ↑ Numbers that cannot be computed
  5. ↑ Is PI a turing computable number?
  6. ↑ Note (a) for The Validity of the Principle: A New Kind of Science
  7. ↑ Computable Number
  8. ↑ 8.0 8.1 On computable numbers with an application to the AlanTuringproblem
  9. ↑ 9.0 9.1 9.2 9.3 How real are real numbers?
  10. ↑ Turing Machines (Stanford Encyclopedia of Philosophy)
  11. ↑ 11.0 11.1 11.2 11.3 Computable number
  12. ↑ Are there any examples of non-computable real numbers?
  13. ↑ 13.0 13.1 13.2 13.3 Talk:Computable number
  14. ↑ Analysis in the Computable Number Field

메타데이터

위키데이터

Spacy 패턴 목록

  • [{'LOWER': 'computable'}, {'LEMMA': 'number'}]
  • [{'LOWER': 'recursive'}, {'LEMMA': 'number'}]
  • [{'LOWER': 'computable'}, {'LEMMA': 'real'}]
원본 주소 "https://wiki.mathnt.net/index.php?title=계산_가능한_수&oldid=51573"