# David Toth

less info
reputation
310
bio website tothchat.com location age member for 2 years, 3 months seen 2 days ago profile views 138

2010 - 2014, Imperial College London, MEng Computing

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

# 228 Actions

 Aug19 comment Is the given Language decidable or recognizable? @user137481 You are correct. Sorry for the confusion. Aug18 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. Aug18 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. Aug18 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? Aug2 revised Do we know that if $\pi$ is normal then there is a proof of it? edited title Aug2 asked Do we know that if $\pi$ is normal then there is a proof of it? Aug2 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? Aug2 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$. Aug2 answered Is the given Language decidable or recognizable? Aug2 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? Jul27 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. Jul27 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? Jul26 revised Is a set $\{ e \in \mathbb{N} | \#\{x \in \mathbb{N} | \phi_e(x) \downarrow \} = \#\mathbb{N}\}$ computable? added 8 characters in body Jul26 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$. Jul25 asked Is a set $\{ e \in \mathbb{N} | \#\{x \in \mathbb{N} | \phi_e(x) \downarrow \} = \#\mathbb{N}\}$ computable? Jul2 awarded Curious Jul2 awarded Inquisitive May21 awarded Yearling May15 suggested suggested edit on Why is cos(90)=0.4 in WebGL? May5 suggested suggested edit on How to calculate the pullback of a $k$-form explicitly