805 reputation
310
bio website tothchat.com
location
age
visits member for 2 years, 3 months
seen 2 days ago

2010 - 2014, Imperial College London, MEng Computing

2014 - 2017, University of Leeds, a PhD candidate in Computability Theory


Aug
19
comment Is the given Language decidable or recognizable?
@user137481 You are correct. Sorry for the confusion.
Aug
18
comment Is the given Language decidable or recognizable?
It may be useful for you to prove: $L$ is recognizable iff $\bar{L}$ is co-recognizable.
Aug
18
comment Is the given Language decidable or recognizable?
@user137481 Beware, it is not always true that $\bar{L}$ recognizable implies $L$ not recognizable. As an example take any decidable set $A$, e.g. $\mathbb{N}$, then both $\mathbb{N}$ and $\bar{\mathbb{N}}=\emptyset$ are recognizable. My proof says that $L$ is not recognizable without any reference that $\bar{L}$ is recognizable. That was only mentioned in the comments to clarify a distinction between definitions of recognizable and co-recognizable. The intuition is that if $M \in L$ then you would need to check $M$ on infinitely many inputs in a finite time, which you cannot,hence $L$ not Re.
Aug
18
comment Is the given Language decidable or recognizable?
@user137481 Recognizable means that if $M \in L$ then given enough computation time you can prove it. A dual notion is if $M \not \in L$ then given enough computation time you can prove it - such a language is called co-recognizable. $L$ is co-recognizable, i.e. the complement $\bar{L}$ is recognizable. But as by my proof $L$ is not recognizable. If you are still confused, could you please include a page number reference to the proof in Sipser's book?
Aug
2
revised Do we know that if $\pi$ is normal then there is a proof of it?
edited title
Aug
2
asked Do we know that if $\pi$ is normal then there is a proof of it?
Aug
2
comment Decidability of a language
@AndreasBlass I assumed $C$ was of the form $\forall$... now I understand what you meant. What about my claim that we do not need to be able to find the counterexample $m$ for $S$ to be decidable. Do you agree with it?
Aug
2
comment Decidability of a language
@AndreasBlass If a conjecture is false, then we agree that it has a counterexample, although it may not be possible to find it. However, since $C$ is fixed in $S$ rather than taken as an input, we do not even need the assumption that the counterexample can be found. We know which $M_k$ decides $S$ iff we can find the first counterexample $m$.
Aug
2
answered Is the given Language decidable or recognizable?
Aug
2
comment Is the given Language decidable or recognizable?
Hint: if an arbitrary program does not halt on some input, how many of its computation steps do you need to verify that this is indeed the case?
Jul
27
comment Is a set $\{ e \in \mathbb{N} | \#\{x \in \mathbb{N} | \phi_e(x) \downarrow \} = \#\mathbb{N}\}$ computable?
Thanks to you all for your answers.
Jul
27
comment Uncomputability of subset relation
@Carl "Given input $n, i_2$ first computes $\phi_e$ on input $i_2$ for $n$ steps." How does $i_2$ know its index if you are still constructing it?
Jul
26
revised Is a set $\{ e \in \mathbb{N} | \#\{x \in \mathbb{N} | \phi_e(x) \downarrow \} = \#\mathbb{N}\}$ computable?
added 8 characters in body
Jul
26
comment Is a set $\{ e \in \mathbb{N} | \#\{x \in \mathbb{N} | \phi_e(x) \downarrow \} = \#\mathbb{N}\}$ computable?
@user150396 $\#A$ denotes the cardinality of a set $A$.
Jul
25
asked Is a set $\{ e \in \mathbb{N} | \#\{x \in \mathbb{N} | \phi_e(x) \downarrow \} = \#\mathbb{N}\}$ computable?
Jul
2
awarded  Curious
Jul
2
awarded  Inquisitive
May
21
awarded  Yearling
May
15
suggested suggested edit on Why is cos(90)=0.4 in WebGL?
May
5
suggested suggested edit on How to calculate the pullback of a $k$-form explicitly