Jump to content

Talk:Specker sequence

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Accompanied by a modulus of convergence

[edit]

“A common way to resolve this difficulty is to consider only sequences that are accompanied by a modulus of convergence;” Does that mean “accompanied by an algorithm computing a modulus of convergence”? --Chricho ∀ (talk) 21:02, 13 February 2012 (UTC)[reply]

Simpler noncomputability proof

[edit]

I will show here simpler proof that limit of Specker sequence is uncomputable. Let us begin with Specker sequence defined same as in article. Define q_inf as limit of sequence. q_inf is equal to Because it is based on non-decidable set, this limit is certainly less than one. Then, if q_inf is computable, then we can in finite time compute n+1th bit of it. This bit is equal to 1 iff n belongs to A. Because of that we can decide if n isn't in this set, which contradicts definition of recursively enumerable but undecidable set. Is this proof sufficient?Wojowu (talk) 18:33, 11 April 2012 (UTC)[reply]

That is basically the same argument in the article. The article simply goes into more depth about how to compute a particular bit of the number (also, note that real numbers don't have "bits", but they do have infinite binary expansions. It is easier to avoid directly mentioning the binary expansion than it is to do it right). Separately, the only reason that we know that the nth bit actually matches the sequence is because we know the limit is not a dyadic rational. The proof in the article avoids having to justify that by looking at how much the partial sum would change instead of looking at the digits of the binary expansion. — Carl (CBM · talk) 19:55, 11 April 2012 (UTC)[reply]

What does "computation of {n}(n)" mean?

[edit]

The definition of the Specker sequence mentions "computation of {n}(n)" but the link points to a page about Turing machines. Ferdinand.kraft (talk) 05:10, 23 February 2021 (UTC)[reply]

I came here with exactly the same question. It looks like {n} might be a specification of the machine, and (n) its input, but that's still very vague. It sure wouldn't hurt to put this concrete example in the prose. DAVilla (talk) 07:29, 21 October 2021 (UTC)[reply]