Open Access. Powered by Scholars. Published by Universities.®

Physical Sciences and Mathematics Commons

Open Access. Powered by Scholars. Published by Universities.®

Computer Sciences

PDF

Series

2017

Institution
Keyword
Publication

Articles 1 - 30 of 1117

Full-Text Articles in Physical Sciences and Mathematics

Semantic Hierarchies For Extracting, Modeling, And Connecting Compliance Requirements In Information Security Control Standards, Matthew L. Hale, Rose F. Gamble Dec 2017

Semantic Hierarchies For Extracting, Modeling, And Connecting Compliance Requirements In Information Security Control Standards, Matthew L. Hale, Rose F. Gamble

Interdisciplinary Informatics Faculty Publications

Companies and government organizations are increasingly compelled, if not required by law, to ensure that their information systems will comply with various federal and industry regulatory standards, such as the NIST Special Publication on Security Controls for Federal Information Systems (NIST SP-800-53), or the Common Criteria (ISO 15408-2). Such organizations operate business or mission critical systems where a lack of or lapse in security protections translates to serious confidentiality, integrity, and availability risks that, if exploited, could result in information disclosure, loss of money, or, at worst, loss of life. To mitigate these risks and ensure that their information systems …


Stable Solution To L 2,1-Based Robust Inductive Matrix Completion And Its Application In Linking Long Noncoding Rnas To Human Diseases, Ashis Kumer Biswas, Dongchul Kim, Mingon Kang, Chris Ding Dec 2017

Stable Solution To L 2,1-Based Robust Inductive Matrix Completion And Its Application In Linking Long Noncoding Rnas To Human Diseases, Ashis Kumer Biswas, Dongchul Kim, Mingon Kang, Chris Ding

Faculty Articles

Backgrounds A large number of long intergenic non-coding RNAs (lincRNAs) are linked to a broad spectrum of human diseases. The disease association with many other lincRNAs still remain as puzzle. Validation of such links between the two entities through biological experiments are expensive. However, a plethora lincRNA-data are available now, thanks to the High Throughput Sequencing (HTS) platforms, Genome Wide Association Studies (GWAS), etc, which opens the opportunity for cutting-edge machine learning and data mining approaches to extract meaningful relationships among lincRNAs and diseases. However, there are only a few in silico lincRNA-disease association inference tools available to date, and …


Stable Solution To L 2,1-Based Robust Inductive Matrix Completion And Its Application In Linking Long Noncoding Rnas To Human Diseases, Ashis Kumer Biswas, Dong-Chul Kim, Mingon Kang, Chris Ding, Jean X. Gao Dec 2017

Stable Solution To L 2,1-Based Robust Inductive Matrix Completion And Its Application In Linking Long Noncoding Rnas To Human Diseases, Ashis Kumer Biswas, Dong-Chul Kim, Mingon Kang, Chris Ding, Jean X. Gao

Computer Science Faculty Publications and Presentations

Backgrounds

A large number of long intergenic non-coding RNAs (lincRNAs) are linked to a broad spectrum of human diseases. The disease association with many other lincRNAs still remain as puzzle. Validation of such links between the two entities through biological experiments are expensive. However, a plethora lincRNA-data are available now, thanks to the High Throughput Sequencing (HTS) platforms, Genome Wide Association Studies (GWAS), etc, which opens the opportunity for cutting-edge machine learning and data mining approaches to extract meaningful relationships among lincRNAs and diseases. However, there are only a few in silico lincRNA-disease association inference tools available to date, and …


Encoding Lexicographical Ordering Constraints In Sat, Wenting Zhao Dec 2017

Encoding Lexicographical Ordering Constraints In Sat, Wenting Zhao

Honors Projects

Symmetry occurs in many constraint satisfaction problems, and it is important to deal with it efficiently and effectively, as it often leads to an exponential number of isomorphic assignments. Symmetric rows and columns in matrices are an important class of symmetries in constraint programming. In this work, we develop a new SAT encoding for partial lexicographical ordering constraints to break symmetries in such places. We also survey all the previous complete lex-leader encodings in literature and translate them into SAT encodings. We perform experimental analysis on how these lex-leader constraints impact the solving of Balanced Incomplete Block Design (BIBD) instances. …


Atomistic Simulations And Network-Based Modeling Of The Hsp90-Cdc37 Chaperone Binding With Cdk4 Client Protein: A Mechanism Of Chaperoning Kinase Clients By Exploiting Weak Spots Of Intrinsically Dynamic Kinase Domains, John Czemeres, Kurt Buse, Gennady M. Verkhivker Dec 2017

Atomistic Simulations And Network-Based Modeling Of The Hsp90-Cdc37 Chaperone Binding With Cdk4 Client Protein: A Mechanism Of Chaperoning Kinase Clients By Exploiting Weak Spots Of Intrinsically Dynamic Kinase Domains, John Czemeres, Kurt Buse, Gennady M. Verkhivker

Mathematics, Physics, and Computer Science Faculty Articles and Research

A fundamental role of the Hsp90 and Cdc37 chaperones in mediating conformational development and activation of diverse protein kinase clients is essential in signal transduction. There has been increasing evidence that the Hsp90-Cdc37 system executes its chaperoning duties by recognizing conformational instability of kinase clients and modulating their folding landscapes. The recent cryo-electron microscopy structure of the Hsp90-Cdc37- Cdk4 kinase complex has provided a framework for dissecting regulatory principles underlying differentiation and recruitment of protein kinase clients to the chaperone machinery. In this work, we have combined atomistic simulations with protein stability and network-based rigidity decomposition analyses to characterize dynamic …


Remote Sensing Of Forests Using Discrete Return Airborne Lidar, Hamid Hamraz, Marco A. Contreras Dec 2017

Remote Sensing Of Forests Using Discrete Return Airborne Lidar, Hamid Hamraz, Marco A. Contreras

Forestry and Natural Resources Faculty Publications

Airborne discrete return light detection and ranging (LiDAR) point clouds covering forested areas can be processed to segment individual trees and retrieve their morphological attributes. Segmenting individual trees in natural deciduous forests, however, remained a challenge because of the complex and multi-layered canopy. In this chapter, we present (i) a robust segmentation method that avoids a priori assumptions about the canopy structure, (ii) a vertical canopy stratification procedure that improves segmentation of understory trees, (iii) an occlusion model for estimating the point density of each canopy stratum, and (iv) a distributed computing approach for efficient processing at the forest level. …


Virtual Reality As A Training Tool To Treat Physical Inactivity In Children, Adam W. Kiefer, David Pincus, Michael J. Richardson, Gregory D. Myer Dec 2017

Virtual Reality As A Training Tool To Treat Physical Inactivity In Children, Adam W. Kiefer, David Pincus, Michael J. Richardson, Gregory D. Myer

Psychology Faculty Articles and Research

Lack of adequate physical activity in children is an epidemic that can result in obesity and other poor health outcomes across the lifespan. Physical activity interventions focused on motor skill competence continue to be developed, but some interventions, such as neuromuscular training (NMT), may be limited in how early they can be implemented due to dependence on the child’s level of cognitive and perceptual-motor development. Early implementation of motor-rich activities that support motor skill development in children is critical for the development of healthy levels of physical activity that carry through into adulthood. Virtual reality (VR) training may be beneficial …


Redesign Of The Bridgewater State University Website, Jordan Rossetti Dec 2017

Redesign Of The Bridgewater State University Website, Jordan Rossetti

Honors Program Theses and Projects

In this thesis, I studied human-computer interaction (HCI), analyzed the usability of the Bridgewater State University website, and redesigned it guided by HCI principles and user experiments. A goal of the project is to apply suggestions from HCI research to the usability analysis of an existing website. I redesigned the website based on this analysis and by conducting user experiments compare the redesign against the existing BSU website. With this project, I redesigned a website that demonstrably improves users’ success at information seeking and navigation while reducing frustration and hassle compared to the current Bridgewater State University (BSU) website. This …


Developing A Virtual Reality Android Application To Remote Explore A Room, Jamie Nelson Dec 2017

Developing A Virtual Reality Android Application To Remote Explore A Room, Jamie Nelson

Honors Program Theses and Projects

Virtual reality is a rapidly growing area of research. Many scholars are emphasizing its importance and creators are designing cheaper equipment to acquire it. The purpose of this research was to create a simple virtual reality mobile application that allows the user to explore a room. For this thesis, we created a robot and, with the help from a fellow researcher, we optimized the robot for this specific task. We programed the robot to move forward in small increments and to spin a platform holding a Go Pro camera. The camera sends a live stream video to an Android mobile …


Exploring The Differences Between Human And Machine Translation, Connor Freitas, Yudong Liu Dec 2017

Exploring The Differences Between Human And Machine Translation, Connor Freitas, Yudong Liu

WWU Honors College Senior Projects

Chinese second language learners of English often use Machine Translators (MT) to translate personal and professional messages from their first language to English. MT’s are not perfect and have historically create messages that lack the cohesiveness and authenticity of natively written English. This paper describes our attempts to quantify the differences between human translation and machine translation in a specific scope with that hope that both MTs and post editing systems can be benefited through awareness of common error and differences between human and machine translations. In order to achieve this we implemented existing algorithms designed to identify common errors …


Tensorviz: Visualizing The Training Of Convolutional Neural Network Using Paraview, Xinyu Chen, Qiang Guan, Xin Liang, Li-Ta Lo, Simon Su, Trilce Estrada, James Ahrens Dec 2017

Tensorviz: Visualizing The Training Of Convolutional Neural Network Using Paraview, Xinyu Chen, Qiang Guan, Xin Liang, Li-Ta Lo, Simon Su, Trilce Estrada, James Ahrens

Computer Science Faculty Research & Creative Works

Deep Convolutional Networks have been very successful in visual recognition tasks recently. Previous works visualize learned features at different layers o help people to understand how CNNs learn visual recognition tasks. However they do not help to accelerate the training process. We use Paraview to provides both qualitative and quantitative visualization that help understand the learning procedure, tune the learning parameters and direct merging and pruning of neural networks.


Tensorviz: Visualizing The Training Of Convolutional Neural Network Using Paraview (Poster), Xinyu Chen, Qiang Guan, Xin Liang, Li-Ta Lo, Simon Su, Trilce Estrada, James Ahrens Dec 2017

Tensorviz: Visualizing The Training Of Convolutional Neural Network Using Paraview (Poster), Xinyu Chen, Qiang Guan, Xin Liang, Li-Ta Lo, Simon Su, Trilce Estrada, James Ahrens

Computer Science Faculty Research & Creative Works

Deep Convolutional Networks have been very successful in visual recognition tasks recently. Lots of previous works aimed to help people to get senses of why those biology-inspired networks achieved such good performances. Deconvnet[1], Guided propagation[2] and a comprehensive visualization tool box[3] can help people to see features learned at different layers of the networks. These works in some extent provided understanding and support for the biology origin of how convolutional networks emulate visual recognition tasks. However, due to the complexity of searching in very high dimensional parameter space, the whole training remains in black-boxes. Normally a large network needs weeks …


Repairing Gaps In Kinari-2 For Large Scale Protein And Flexibility Analysis Applications, Magdalena Metlicka, Mojtaba Nouri Bygi, Ileana Streinu Dec 2017

Repairing Gaps In Kinari-2 For Large Scale Protein And Flexibility Analysis Applications, Magdalena Metlicka, Mojtaba Nouri Bygi, Ileana Streinu

Computer Science: Faculty Publications

Pebble game rigidity analysis is a combinatorial method, implemented in our free web server KinariWeb, for extracting protein rigidity and flexibility information without performing costly molecular dynamics simulations. Due to the idiosynchrasies of the data in the Protein Data Bank (PDB), Kinari succeeds only on a fraction of the available files. Motivated by large scale applications, aiming at processing almost all the PDB files, we have recently developed a faster and more robust version, the phased pebble game algorithm. It is specifically designed to take advantage of the sequential structure of biopolymers. However, the structural data available in the Protein …


Real-Time Indoor Assistive Localization With Mobile Omnidirectional Vision And Cloud Gpu Acceleration, Feng Hu, Zhigang Zhu, Jeury Mejia, Hao Tang Dec 2017

Real-Time Indoor Assistive Localization With Mobile Omnidirectional Vision And Cloud Gpu Acceleration, Feng Hu, Zhigang Zhu, Jeury Mejia, Hao Tang

Publications and Research

In this paper we propose a real-time assistive localization approach to help blind and visually impaired people in navigating an indoor environment. The system consists of a mobile vision front end with a portable panoramic lens mounted on a smart phone, and a remote image feature-based database of the scene on a GPU-enabled server. Compact and elective omnidirectional image features are extracted and represented in the smart phone front end, and then transmitted to the server in the cloud. These features of a short video clip are used to search the database of the indoor environment via image-based indexing to …


The Ability Of Different Imputation Methods To Preserve The Significant Genes And Pathways In Cancer, Rosa Aghdam, Taban Baghfalaki, Pegah Khosravi, Elnaz Saberi Ansari Dec 2017

The Ability Of Different Imputation Methods To Preserve The Significant Genes And Pathways In Cancer, Rosa Aghdam, Taban Baghfalaki, Pegah Khosravi, Elnaz Saberi Ansari

Publications and Research

Deciphering important genes and pathways from incomplete gene expression data could facilitate a better understanding of cancer. Different imputation methods can be applied to estimate the missing values. In our study, we evaluated various imputation methods for their performance in preserving significant genes and pathways. In the first step, 5% genes are considered in random for two types of ignorable and non-ignorable missingness mechanisms with various missing rates. Next, 10 well-known imputation methods were applied to the complete datasets. The significance analysis of microarrays (SAM) method was applied to detect the significant genes in rectal and lung cancers to showcase …


Understanding Sleep In Pediatric Patients With Sickle Cell Disease Admitted For Vaso-Occlusive Pain Crisis Through Objective Data, Kalindi Narine, Fan Yang, Tanvi Banerjee, Jude Jonassaint, Nirmish Shah Dec 2017

Understanding Sleep In Pediatric Patients With Sickle Cell Disease Admitted For Vaso-Occlusive Pain Crisis Through Objective Data, Kalindi Narine, Fan Yang, Tanvi Banerjee, Jude Jonassaint, Nirmish Shah

Computer Science and Engineering Faculty Publications

Sickle cell disease (SCD) is an inherited red cell disorder that leads to sickling of red blood cells, anemia and vaso-occlusion. The most common reason for hospitalization and morbidity in children is pain due to vaso-occlusive crisis (VOC). Importantly, poor sleep quality can lead to increased pain the subsequent day and nocturnal pain leads to reduced deep sleep, both which can then modify pain sensitivity. Studies using sleep diaries have shown this cyclical relationship between sleep and pain. Frequent occurrences of restless sleep are therefore believed to contribute to an increased severity and intensity of pain episodes. There is very …


College Of Engineering Senior Design Competition Fall 2017, University Of Nevada, Las Vegas Dec 2017

College Of Engineering Senior Design Competition Fall 2017, University Of Nevada, Las Vegas

Fred and Harriet Cox Senior Design Competition Projects

Part of every UNLV engineering student’s academic experience, the senior design project stimulates engineering innovation and entrepreneurship. Each student in their senior year chooses, plans, designs, and prototypes a product in this required element of the curriculum. A capstone to the student’s educational career, the senior design project encourages the student to use everything learned in the engineering program to create a practical, real world solution to an engineering challenge. The senior design competition helps focus the senior students in increasing the quality and potential for commercial application for their design projects. Judges from local industry evaluate the projects on …


Severity Of Acute Infectious Mononucleosis Correlates With Cross- Reactive Influenza Cd8 T-Cell Receptor Repertoires, Nuray Aslan, Levi B. Watkin, Anna Gil, Rabinarayan Mishra, Fransenio G. Clark, Raymond M. Welsh, Dario Ghersi, Katherine Luzuriaga, Liisa K. Selin Dec 2017

Severity Of Acute Infectious Mononucleosis Correlates With Cross- Reactive Influenza Cd8 T-Cell Receptor Repertoires, Nuray Aslan, Levi B. Watkin, Anna Gil, Rabinarayan Mishra, Fransenio G. Clark, Raymond M. Welsh, Dario Ghersi, Katherine Luzuriaga, Liisa K. Selin

Interdisciplinary Informatics Faculty Publications

Fifty years after the discovery of Epstein-Barr virus (EBV), it remains unclear how primary infection with this virus leads to massive CD8 T-cell expansion and acute infectious mononucleosis (AIM) in young adults. AIM can vary greatly in severity, from a mild transient influenza-like illness to a prolonged severe syndrome. We questioned whether expansion of a unique HLA-A2.01-restricted, cross-reactive CD8 T-cell response between influenza virus A-M158 (IAV-M1) and EBV BMLF1280 (EBV-BM) could modulate the immune response to EBV and play a role in determining the severity of AIM in 32 college students. Only ex vivo total IAV-M1 and IAV-M1+EBV-BM cross-reactive tetramer+ …


Constrained Sequence Alignment, Kyle Daling Dec 2017

Constrained Sequence Alignment, Kyle Daling

WWU Honors College Senior Projects

Constrained Sequence Alignment: A new algorithm designed to help biologists produce better alignment for protein sequences.


A Restful Framework For Writing, Running, And Evaluating Code In Multiple Academic Settings, Christopher Ban Dec 2017

A Restful Framework For Writing, Running, And Evaluating Code In Multiple Academic Settings, Christopher Ban

MS in Computer Science Project Reports

In academia, students and professors want a well-structured and implemented framework for writing and running code in both testing and learning environments. The current limitations of the paper and pencil medium have led to the creation of many different online grading systems. However, no known system provides all of the essential features our client is interested in. Our system, developed in conjunction with Doctor Halterman, offers the ability to build modules from flat files, allow code to be compiled and run in the browser, provide users with immediate feedback, support multiple languages, and offer a module designed specifically for an …


Why Rectified Linear Neurons Are Efficient: Symmetry-Based, Complexity-Based, And Fuzzy-Based Explanations, Olac Fuentes, Justin Parra, Elizabeth Y. Anthony, Vladik Kreinovich Dec 2017

Why Rectified Linear Neurons Are Efficient: Symmetry-Based, Complexity-Based, And Fuzzy-Based Explanations, Olac Fuentes, Justin Parra, Elizabeth Y. Anthony, Vladik Kreinovich

Departmental Technical Reports (CS)

Traditionally, neural networks used a sigmoid activation function. Recently, it turned out that piecewise linear activation functions are much more efficient -- especially in deep learning applications. However, so far, there have been no convincing theoretical explanation for this empirical efficiency. In this paper, we show that, by using different uncertainty techniques, we can come up with several explanations for the efficiency of piecewise linear neural networks. The existence of several different explanations makes us even more confident in our results -- and thus, in the efficiency of piecewise linear activation functions.


Z-Numbers: How They Describe Student Confidence And How They Can Explain (And Improve) Laplacian And Schroedinger Eigenmap Dimension Reduction In Data Analysis, Vladik Kreinovich, Olga Kosheleva, Michael Zakharevich Dec 2017

Z-Numbers: How They Describe Student Confidence And How They Can Explain (And Improve) Laplacian And Schroedinger Eigenmap Dimension Reduction In Data Analysis, Vladik Kreinovich, Olga Kosheleva, Michael Zakharevich

Departmental Technical Reports (CS)

Experts have different degrees of confidence in their statements. To describe these different degrees of confidence, Lotfi A. Zadeh proposed the notion of a Z-number: a fuzzy set (or other type of uncertainty) supplemented by a degree of confidence in the statement corresponding to fuzzy sets. In this chapter, we show that Z-numbers provide a natural formalization of the competence-vs-confidence dichotomy, which is especially important for educating low-income students. We also show that Z-numbers provide a natural theoretical explanation for several empirically heuristic techniques of dimension reduction in data analysis, such as Laplacian and Schroedinger eigenmaps, and, moreover, show how …


Why Deep Learning Methods Use Kl Divergence Instead Of Least Squares: A Possible Pedagogical Explanation, Olga Kosheleva, Vladik Kreinovich Dec 2017

Why Deep Learning Methods Use Kl Divergence Instead Of Least Squares: A Possible Pedagogical Explanation, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

In most applications of data processing, we select the parameters that minimize the mean square approximation error. The same Least Squares approach has been used in the traditional neural networks. However, for deep learning, it turns out that an alternative idea works better -- namely, minimizing the Kullback-Leibler (KL) divergence. The use of KL divergence is justified if we predict probabilities, but the use of this divergence has been successful in other situations as well. In this paper, we provide a possible explanation for this empirical success. Namely, the Least Square approach is optimal when the approximation error is normally …


Why Triangular Membership Functions Are Often Efficient In F-Transform Applications: Relation To Interval Uncertainty\\ And Haar Wavelets, Olga Kosheleva, Vladik Kreinovich Dec 2017

Why Triangular Membership Functions Are Often Efficient In F-Transform Applications: Relation To Interval Uncertainty\\ And Haar Wavelets, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

Fuzzy techniques describe expert opinions. At first glance, we would therefore expect that the more accurately the corresponding membership functions describe the expert's opinions, the better the corresponding results. In practice, however, contrary to these expectations, the simplest -- and not very accurate -- triangular membership functions often work the best. In this paper, on the example of the use of membership functions in F-transform techniques, we provide a possible theoretical explanation for this surprising empirical phenomenon.


Beyond Integration: A Symmetry-Based Approach To Reaching Stationarity In Economic Time Series, Songsak Sriboonchitta, Olga Kosheleva, Vladik Kreinovich Dec 2017

Beyond Integration: A Symmetry-Based Approach To Reaching Stationarity In Economic Time Series, Songsak Sriboonchitta, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

Many efficient data processing techniques assume that the corresponding process is stationary. However, in areas like economics, most processes are not stationery: with the exception of stagnation periods, economies usually grow. A known way to apply stationarity-based methods to such processes -- integration -- is based on the fact that often, while the process itself is not stationary, its first or second differences are stationary. This idea works when the trend polynomially depends on time. In practice, the trend is usually non-polynomial: it is often exponentially growing, with cycles added. In this paper, we shod how integration techniques can be …


Why Sparse?, Thongchai Dumrongpokaphan, Olga Kosheleva, Vladik Kreinovich, Aleksandra Belina Dec 2017

Why Sparse?, Thongchai Dumrongpokaphan, Olga Kosheleva, Vladik Kreinovich, Aleksandra Belina

Departmental Technical Reports (CS)

In many situations, a solution to a practical problem is sparse, i.e., corresponds to the case when most of the parameters describing the solution are zeros, and only a few attain non-zero values. This surprising empirical phenomenon helps solve the corresponding problems -- but it remains unclear why this phenomenon happens. In this paper, we provide a possible theoretical explanation for this mysterious phenomenon.


How To Best Apply Neural Networks In Geosciences: Towards Optimal "Averaging" In Dropout Training, Afshin Gholamy, Justin Parra, Vladik Kreinovich, Olac Fuentes, Elizabeth Y. Anthony Dec 2017

How To Best Apply Neural Networks In Geosciences: Towards Optimal "Averaging" In Dropout Training, Afshin Gholamy, Justin Parra, Vladik Kreinovich, Olac Fuentes, Elizabeth Y. Anthony

Departmental Technical Reports (CS)

The main objectives of geosciences is to find the current state of the Earth -- i.e., solve the corresponding inverse problems -- and to use this knowledge for predicting the future events, such as earthquakes and volcanic eruptions. In both inverse and prediction problems, often, machine learning techniques are very efficient, and at present, the most efficient machine learning technique is deep neural training. To speed up this training, the current learning algorithms use dropout techniques: they train several sub-networks on different portions of data, and then "average" the results. A natural idea is to use arithmetic mean for this …


Why Taylor Models And Modified Taylor Models Are Empirically Successful: A Symmetry-Based Explanation, Mioara Joldes, Christoph Lauter, Martine Ceberio, Olga Kosheleva, Vladik Kreinovich Dec 2017

Why Taylor Models And Modified Taylor Models Are Empirically Successful: A Symmetry-Based Explanation, Mioara Joldes, Christoph Lauter, Martine Ceberio, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

In this paper, we show that symmetry-based ideas can explain the empirical success of Taylor models and modified Taylor models in representing uncertainty.


How To Store Tensors In Computer Memory: An Observation, Martine Ceberio, Vladik Kreinovich Dec 2017

How To Store Tensors In Computer Memory: An Observation, Martine Ceberio, Vladik Kreinovich

Departmental Technical Reports (CS)

In this paper, after explaining the need to use tensors in computing, we analyze the question of how to best store tensors in computer memory. Somewhat surprisingly, with respect to a natural optimality criterion, the standard way of storing tensors turns out to be one of the optimal ones.


How To Make A Proof Of Halting Problem More Convincing: A Pedagogical Remark, Benjamin W. Robertson, Olga Kosheleva, Vladik Kreinovich Dec 2017

How To Make A Proof Of Halting Problem More Convincing: A Pedagogical Remark, Benjamin W. Robertson, Olga Kosheleva, Vladik Kreinovich

Departmental Technical Reports (CS)

As an example of an algorithmically undecidable problem, most textbooks list the impossibility to check whether a given program halts on given data. A usual proof of this result is based on the assumption that the hypothetical halt-checker works for all programs. To show that a halt-checker is impossible, we design an auxiliary program for which the existence of such a halt-checker leads to a contradiction. However, this auxiliary program is usually very artificial. So, a natural question arises: what if we only require that the halt-checker work for reasonable programs? In this paper, we show that even with such …